138

J'essaye d'écrire une fonction qui fait ce qui suit:

prend un tableau d'entiers comme argument (par exemple [1,2,3,4])
crée un tableau de toutes les permutations possibles de [1,2,3,4], chaque permutation ayant une longueur de 4

la fonction ci-dessous (je l'ai trouvée en ligne) le fait en prenant une chaîne comme argument et en retournant toutes les permutations de cette chaîne

Je ne pouvais pas comprendre comment le modifier pour le faire fonctionner avec un tableau d'entiers, (je pense que cela a quelque chose à voir avec la façon dont certaines des méthodes fonctionnent différemment sur les chaînes que sur les entiers, mais je ne suis pas sûr. ..)

var permArr = [], usedChars = [];
function permute(input) {
  var i, ch, chars = input.split("");
  for (i = 0; i < chars.length; i++) {
    ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length == 0)
      permArr[permArr.length] = usedChars.join("");
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};

Remarque: je cherche à faire en sorte que la fonction renvoie des tableaux d' entiers , pas un tableau de chaînes .

J'ai vraiment besoin que la solution soit en JavaScript. J'ai déjà compris comment faire cela en python

javascript permutation poivre
la source

106

Si vous remarquez, le code divise en fait les caractères en un tableau avant d'effectuer toute permutation, vous supprimez donc simplement l'opération de jointure et de fractionnement.

var permArr = [],
  usedChars = [];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      permArr.push(usedChars.slice());
    }
    permute(input);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};


document.write(JSON.stringify(permute([5, 3, 7, 1])));

Développer l'extrait

Andreas Wong
la source

@SiGanteng. Quelque chose de bizarre m'arrive en essayant d'utiliser votre fonction. Je le garde dans un .js où j'ai toute ma "fonction de manipulation de liste". Si je l'utilise avec permute ([1,2,3]), puis permute ([4,5,6]), la sortie du dernier a toujours le résultat, sortie du premier. Une idée de comment résoudre ce problème? Merci beaucoup !

500

3

Il y a une nouvelle question à propos de cette réponse .

Anderson Green

15

Accéder aux globaux dans votre fonction, mauvaise forme!

Shmiddty

123

Un peu tard, mais j'aime ajouter une version un peu plus élégante ici. Peut être n'importe quel tableau ...

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

Ajout d'une version ES6 (2015). Ne modifie pas non plus le tableau d'entrée d'origine. Fonctionne dans la console dans Chrome ...

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

Alors...

permutator(['c','a','t']);

Rendements ...

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

Et...

permutator([1,2,3]);

Rendements ...

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]

délimité
la source

1

Si vous avez une fonction factorielle à portée de main (comme cela est assez probable compte tenu du fait que vous avez affaire à des permutations), vous pouvez l'accélérer en modifiant l'initialisation de la portée externe en var results = new Array(factorial(inputArr.length)), length=0, puis la remplacer results.push(…)parresults[length++]=…

Cyoce

1

Que fait la ligne var cur, memo = memo || [];?

Ricevind

2

@ user2965967 Il déclare cur et memo, et initialise memo comme étant la valeur de memo, sauf s'il est faux (y compris indéfini), auquel cas ce sera un tableau vide. En d'autres termes, c'est un moyen moins qu'idéal de fournir au paramètre de fonction une valeur par défaut.

M. Lavalamp

Cela modifie le tableau d'origine.

Shmiddty

2

est le slice()dans permute(curr.slice(), m.concat(next))vraiment nécessaire?

Yoav

82

L'algorithme très efficace suivant utilise la méthode de Heap pour générer toutes les permutations de N éléments avec une complexité d'exécution en O (N!):

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

console.log(permute([1, 2, 3]));

Développer l'extrait

Le même algorithme implémenté en générateur avec complexité spatiale en O (N):

Afficher l'extrait de code

function* permute(permutation) {
  var length = permutation.length,
      c = Array(length).fill(0),
      i = 1, k, p;

  yield permutation.slice();
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      yield permutation.slice();
    } else {
      c[i] = 0;
      ++i;
    }
  }
}

// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);

// Simple array conversion:
var permutations = [...permute([1, 2, 3])];

Développer l'extrait

Comparaison des performances

N'hésitez pas à ajouter votre implémentation aux éléments suivants tests benchmark.js :

Afficher l'extrait de code

function permute_SiGanteng(input) {
  var permArr = [],
    usedChars = [];

  function permute(input) {
    var i, ch;
    for (i = 0; i < input.length; i++) {
      ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      permute(input);
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr
  }
  return permute(input);
}

function permute_delimited(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];
    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }
    return results;
  }
  return permute(inputArr);
}

function permute_monkey(inputArray) {
  return inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
}

function permute_Oriol(input) {
  var permArr = [],
    usedChars = [];
  return (function main() {
    for (var i = 0; i < input.length; i++) {
      var ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      main();
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr;
  })();
}

function permute_MarkusT(input) {
  function permutate(array, callback) {
      function p(array, index, callback) {
          function swap(a, i1, i2) {
              var t = a[i1];
              a[i1] = a[i2];
              a[i2] = t;
          }
          if (index == array.length - 1) {
              callback(array);
              return 1;
          } else {
              var count = p(array, index + 1, callback);
              for (var i = index + 1; i < array.length; i++) {
                  swap(array, i, index);
                  count += p(array, index + 1, callback);
                  swap(array, i, index);
              }
              return count;
          }
      }
      if (!array || array.length == 0) {
          return 0;
      }
      return p(array, 0, callback);
  }
  var result = [];
  permutate(input, function(a) {
      result.push(a.slice(0));
  });
  return result;
}

function permute_le_m(permutation) {
  var length = permutation.length,
  		result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;
  
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i],
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

function permute_Urielzen(arr) {
    var finalArr = [];
    var iterator = function (arrayTaken, tree) {
        for (var i = 0; i < tree; i++) {
            var temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else { iterator(temp, tree + 1); }
        }
    }
    iterator(arr, 1); return finalArr;
}

function permute_Taylor_Hakes(arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permute_Taylor_Hakes(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

var Combinatorics = (function () {
    'use strict';
    var version = "0.5.2";
    /* combinatory arithmetics */
    var P = function(m, n) {
        var p = 1;
        while (n--) p *= m--;
        return p;
    };
    var C = function(m, n) {
        if (n > m) {
            return 0;
        }
        return P(m, n) / P(n, n);
    };
    var factorial = function(n) {
        return P(n, n);
    };
    var factoradic = function(n, d) {
        var f = 1;
        if (!d) {
            for (d = 1; f < n; f *= ++d);
            if (f > n) f /= d--;
        } else {
            f = factorial(d);
        }
        var result = [0];
        for (; d; f /= d--) {
            result[d] = Math.floor(n / f);
            n %= f;
        }
        return result;
    };
    /* common methods */
    var addProperties = function(dst, src) {
        Object.keys(src).forEach(function(p) {
            Object.defineProperty(dst, p, {
                value: src[p],
                configurable: p == 'next'
            });
        });
    };
    var hideProperty = function(o, p) {
        Object.defineProperty(o, p, {
            writable: true
        });
    };
    var toArray = function(f) {
        var e, result = [];
        this.init();
        while (e = this.next()) result.push(f ? f(e) : e);
        this.init();
        return result;
    };
    var common = {
        toArray: toArray,
        map: toArray,
        forEach: function(f) {
            var e;
            this.init();
            while (e = this.next()) f(e);
            this.init();
        },
        filter: function(f) {
            var e, result = [];
            this.init();
            while (e = this.next()) if (f(e)) result.push(e);
            this.init();
            return result;
        },
        lazyMap: function(f) {
            this._lazyMap = f;
            return this;
        },
        lazyFilter: function(f) {
            Object.defineProperty(this, 'next', {
                writable: true
            });
            if (typeof f !== 'function') {
                this.next = this._next;
            } else {
                if (typeof (this._next) !== 'function') {
                    this._next = this.next;
                }
                var _next = this._next.bind(this);
                this.next = (function() {
                    var e;
                    while (e = _next()) {
                        if (f(e))
                            return e;
                    }
                    return e;
                }).bind(this);
            }
            Object.defineProperty(this, 'next', {
                writable: false
            });
            return this;
        }

    };
    /* power set */
    var power = function(ary, fun) {
        var size = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                that.index = 0;
            },
            nth: function(n) {
                if (n >= size) return;
                var i = 0,
                    result = [];
                for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            },
            next: function() {
                return this.nth(this.index++);
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* combination */
    var nextIndex = function(n) {
        var smallest = n & -n,
            ripple = n + smallest,
            new_smallest = ripple & -ripple,
            ones = ((new_smallest / smallest) >> 1) - 1;
        return ripple | ones;
    };
    var combination = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var first = (1 << nelem) - 1,
            size = C(ary.length, nelem),
            maxIndex = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                this.index = first;
            },
            next: function() {
                if (this.index >= maxIndex) return;
                var i = 0,
                    n = this.index,
                    result = [];
                for (; n; n >>>= 1, i++) {
                    if (n & 1) result[result.length] = this[i];
                }

                this.index = nextIndex(this.index);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* permutation */
    var _permutation = function(ary) {
        var that = ary.slice(),
            size = factorial(that.length);
        that.index = 0;
        that.next = function() {
            if (this.index >= size) return;
            var copy = this.slice(),
                digits = factoradic(this.index, this.length),
                result = [],
                i = this.length - 1;
            for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
            this.index++;
            return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
        };
        return that;
    };
    // which is really a permutation of combination
    var permutation = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var size = P(ary.length, nelem),
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'cmb');
        hideProperty(that, 'per');
        addProperties(that, {
            valueOf: function() {
                return size;
            },
            init: function() {
                this.cmb = combination(ary, nelem);
                this.per = _permutation(this.cmb.next());
            },
            next: function() {
                var result = this.per.next();
                if (!result) {
                    var cmb = this.cmb.next();
                    if (!cmb) return;
                    this.per = _permutation(cmb);
                    return this.next();
                }
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };

    /* export */
    var Combinatorics = Object.create(null);
    addProperties(Combinatorics, {
        C: C,
        P: P,
        factorial: factorial,
        factoradic: factoradic,
        permutation: permutation,
    });
    return Combinatorics;
})();

function permute_Technicalbloke(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])
    .map(value=>accumulator.push([inputArray[index],value]));
    return accumulator;
  },[]);
}

var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];

suite.add('permute_SiGanteng', function() {
    permute_SiGanteng(input);
  })
  .add('permute_delimited', function() {
    permute_delimited(input);
  })
  .add('permute_monkey', function() {
    permute_monkey(input);
  })
  .add('permute_Oriol', function() {
    permute_Oriol(input);
  })
  .add('permute_MarkusT', function() {
    permute_MarkusT(input);
  })
  .add('permute_le_m', function() {
    permute_le_m(input);
  })
  .add('permute_Urielzen', function() {
    permute_Urielzen(input);
  })
  .add('permute_Taylor_Hakes', function() {
    permute_Taylor_Hakes(input);
  })
  .add('permute_Combinatorics', function() {
    Combinatorics.permutation(input).toArray();
  })
  .add('permute_Technicalbloke', function() {
    permute_Technicalbloke(input);
  })
  .on('cycle', function(event) {
    console.log(String(event.target));
  })
  .on('complete', function() {
    console.log('Fastest is ' + this.filter('fastest').map('name'));
  })
  .run({async: true});

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

Développer l'extrait

Résultats d'exécution pour Chrome 48:

99.152ms Cet algorithme
153.115ms MarkusT
401.255ms js-combinatoire
497,037 ms Urielzen
925,669 ms Oriol
1026,571 ms ms SiGanteng
2529,841 ms délimité
3992,622 ms Singe
4514,665 ms Oriol

le_m
la source

1

Comment ce code peut-il être modifié pour fournir des résultats pour un n = 2 fixe? Par exemple, supposons que nous ayons un ensemble de trois lettres: A, B et C. Nous pourrions demander combien de façons nous pouvons organiser 2 lettres à partir de cet ensemble. Chaque arrangement possible serait un exemple de permutation. La liste complète des permutations possibles serait: AB, AC, BA, BC, CA et CB.

a4xrbj1

1

@ a4xrbj1 Voir par exemple l'exemple de code dans cette question: stackoverflow.com/questions/37892738/… - ou demandez-vous spécifiquement de modifier cette méthode (de Heap)?

le_m

@le_m oui, en utilisant spécifiquement cette méthode (de Heap) car elle est si rapide

a4xrbj1

@ a4xrbj1 Je calculerais toutes les combinaisons de longueur fixe n (par exemple AB, AC, BC pour n = 2) en utilisant une stratégie similaire au lien donné ci-dessus (voir aussi stackoverflow.com/questions/127704/… ) puis pour chaque combinaison calculer toutes ses permutations en utilisant la méthode de Heap. Des cas particuliers tels que n = 2 peuvent bien entendu être optimisés.

le_m

1

La version du générateur ne fonctionne pas correctement, vous devriez le faire yield permutation.slice()si vous ne découpez pas, vous n'obtiendrez que la dernière permutation calculée.

Beldar

41

var inputArray = [1, 2, 3];

var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);


alert(JSON.stringify(result));

singe
la source

10

Wow, malgré sa lacune et son manque de documentation, je pense que c'est la réponse la plus élégante. Mon explication de cet algorithme est la suivante: pour chaque élément du tableau (réduire), sélectionnez tous les autres éléments, permutez-les (récursivement) et concattez avec cet élément.

aaron

J'ai essayé cette solution ici: codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/ ... J'ai déballé le code de golf original en un code lisible, mais c'est essentiellement le même. Le problème avec cela est qu'il produit des doublons, et j'ai dû faire un complément .filter(uniq)sur le résultat.

Andrey Mikhaylov - lolmaus

1

y a-t-il un parallèle lisp au concept [1,2,3].length == 3 && "foo" || "bar"ou [1,2].length == 3 && "foo" || "bar"oh mon Dieu! il y a! (or (and (= 3 2) (print "hello!")) (print "goodbye"))

Dmitry

@ lolmaus-AndreyMikhaylov comment supprimer la duplication s'il vous plaît mettre à jour la réponse si vous le pouvez

Pardeep Jain

@PardeepJain J'ai donné un lien vers ma solution ci-dessus.

Andrey Mikhaylov - lolmaus

21

J'ai amélioré la réponse de SiGanteng .

Maintenant, il est possible d'appeler permuteplus d'une fois, car permArret usedCharssont effacés à chaque fois.

function permute(input) {
    var permArr = [],
        usedChars = [];
    return (function main() {
        for (var i = 0; i < input.length; i++) {
            var ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main();
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr;
    })();
}

Afficher l'extrait de code

function permute(input) {
  var permArr = [],
      usedChars = [];
  return (function main() {
    for (var i = 0; i < input.length; i++) {
      var ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      main();
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr;
  })();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));

Développer l'extrait

Oriol
la source

10

La fonction suivante permute un tableau de n'importe quel type et appelle une fonction de rappel spécifiée sur chaque permutation trouvée:

/*
  Permutate the elements in the specified array by swapping them
  in-place and calling the specified callback function on the array
  for each permutation.

  Return the number of permutations.

  If array is undefined, null or empty, return 0.

  NOTE: when permutation succeeds, the array should be in the original state
  on exit!
*/
  function permutate(array, callback) {
    // Do the actual permuation work on array[], starting at index
    function p(array, index, callback) {
      // Swap elements i1 and i2 in array a[]
      function swap(a, i1, i2) {
        var t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
      }

      if (index == array.length - 1) {
        callback(array);
        return 1;
      } else {
        var count = p(array, index + 1, callback);
        for (var i = index + 1; i < array.length; i++) {
          swap(array, i, index);
          count += p(array, index + 1, callback);
          swap(array, i, index);
        }
        return count;
      }
    }

    if (!array || array.length == 0) {
      return 0;
    }
    return p(array, 0, callback);
  }

Si vous l'appelez comme ceci:

  // Empty array to hold results
  var result = [];
  // Permutate [1, 2, 3], pushing every permutation onto result[]
  permutate([1, 2, 3], function (a) {
    // Create a copy of a[] and add that to result[]
    result.push(a.slice(0));
  });
  // Show result[]
  document.write(result);

Je pense qu'il fera exactement ce dont vous avez besoin - remplir un tableau appelé resultavec les permutations du tableau [1, 2, 3]. Le résultat est:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

Code un peu plus clair sur JSFiddle: http://jsfiddle.net/MgmMg/6/

MarkusT
la source

10

La plupart des réponses à cette question utilisent des opérations coûteuses telles que les insertions et les suppressions continues d'éléments dans un tableau, ou la copie de tableaux de manière répétitive.

Au lieu de cela, c'est la solution de retour en arrière typique:

function permute(arr) {
  var results = [],
      l = arr.length,
      used = Array(l), // Array of bools. Keeps track of used items
      data = Array(l); // Stores items of the current permutation
  (function backtracking(pos) {
    if(pos == l) return results.push(data.slice());
    for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
      used[i] = true;      // Mark item as used
      data[pos] = arr[i];  // Assign item at the current position
      backtracking(pos+1); // Recursive call
      used[i] = false;     // Mark item as not used
    }
  })(0);
  return results;
}

permute([1,2,3,4]); // [  [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1]  ]

Étant donné que le tableau de résultats sera énorme, il peut être judicieux d'itérer les résultats un par un au lieu d'allouer toutes les données simultanément. Dans ES6, cela peut être fait avec des générateurs:

function permute(arr) {
  var l = arr.length,
      used = Array(l),
      data = Array(l);
  return function* backtracking(pos) {
    if(pos == l) yield data.slice();
    else for(var i=0; i<l; ++i) if(!used[i]) {
      used[i] = true;
      data[pos] = arr[i];
      yield* backtracking(pos+1);
      used[i] = false;
    }
  }(0);
}

var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}

Oriol
la source

6

C'est une tâche intéressante et voici ma contribution. C'est très simple et rapide. Si vous êtes intéressé, veuillez rester avec moi et continuer à lire.

Si vous souhaitez effectuer ce travail rapidement, vous devez absolument vous lancer dans la programmation dynamique. Ce qui signifie que vous devez oublier les approches récursives. Ça c'est sûr...

OK le code de le_m qui utilise la méthode de Heap semble être le plus rapide à ce jour. Eh bien, je n'ai pas de nom pour mon algorithme, je ne sais pas s'il a déjà été implémenté ou non mais c'est très simple et rapide. Comme pour toutes les approches de programmation dynamique, nous allons commencer par le problème le plus simple et aller pour le résultat final.

En supposant que nous avons un tableau de a = [1,2,3]nous commencerons par

r = [[1]]; // result
t = [];    // interim result

Suivez ensuite ces trois étapes;

Pour chaque élément de notre rtableau (résultat), nous ajouterons l'élément suivant du tableau d'entrée.
Nous allons faire pivoter chaque élément de sa longueur plusieurs fois et stocker chaque instance dans le tableau de résultats intermédiaire t. (enfin sauf pour le premier pour ne pas perdre de temps avec 0 rotation)
Une fois que nous avons terminé avec tous les éléments du rtableau intermédiaire, nous tdevrions contenir le niveau de résultats suivant, donc nous faisons r = t; t = [];et continuons jusqu'à la longueur du tableau d'entrée a.

Voici donc nos étapes;

r array   | push next item to |  get length many rotations
          |  each sub array   |       of each subarray
-----------------------------------------------------------
[[1]]     |     [[1,2]]       |     [[1,2],[2,1]]
----------|-------------------|----------------------------
[[1,2],   |     [[1,2,3],     |     [[1,2,3],[2,3,1],[3,1,2],
 [2,1]]   |      [2,1,3]]     |      [2,1,3],[1,3,2],[3,2,1]]
----------|-------------------|----------------------------
previous t|                   |
-----------------------------------------------------------

Alors voici le code

function perm(a){
  var r = [[a[0]]],
      t = [],
      s = [];
  if (a.length <= 1) return a;
  for (var i = 1, la = a.length; i < la; i++){
    for (var j = 0, lr = r.length; j < lr; j++){
      r[j].push(a[i]);
      t.push(r[j]);
      for(var k = 1, lrj = r[j].length; k < lrj; k++){
        for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
        t[t.length] = s;
        s = [];
      }
    }
    r = t;
    t = [];
  }
  return r;
}

var arr = [0,1,2,4,5];
console.log("The length of the permutation is:",perm(arr).length);
console.time("Permutation test");
for (var z = 0; z < 2000; z++) perm(arr);
console.timeEnd("Permutation test");

Développer l'extrait

Dans plusieurs tests, je l'ai vu résoudre les 120 permutations de [0,1,2,3,4] pour 2000 fois en 25 ~ 35ms.

Redu
la source

1

Il semble fonctionner très vite, parfois plus vite, parfois plus lentement que la méthode Heap sur FF / Ubuntu pour des itérations de longueur / préchauffage différentes, etc. Il faudrait un jsperf pour voir les résultats pour différents moteurs.

le_m

1

@le_m OK, j'ai fait un test @JSBen sur Ubuntu & AMD CPU: Avec Chrome rotatePerm(celui ci-dessus), c'est toujours 1,2 plus rapide. Avec FF, il n'y a pas de cohérence. Après plusieurs tests, c'est parfois heapPerm2 fois plus rapide, parfois rotatePerm1,1 fois plus rapide. Avec d'autres navigateurs de kit Web tels que Opera ou Epiphany, il rotatePerms'avère toujours 1,1 fois plus rapide. Cependant, avec Edge, heapPermc'est toujours 1,2 fois plus rapide à chaque fois.

Réduire

1

Agréable! Il semble que - au moins sur FF / Ubuntu - les performances de la méthode de tas dépendent principalement des performances de la copie de tableau. J'ai modifié votre benchmark pour comparer slicing vs pushing: jsben.ch/#/x7mYh - sur FF et pour les petits tableaux d'entrée, pousser semble beaucoup plus rapide

le_m

2

Ce serait formidable si la méthode du tas pouvait être battue en termes de performances. À propos, votre méthode génère le même résultat que l'algorithme de Langdon (page 16) du même article de 1977 que j'ai utilisé comme référence pour la méthode de Heap: homepage.math.uiowa.edu/~goodman/22m150.dir/2007/…

le_m

2

@le_m Je viens de vérifier et cela semble être la même chose. Il me semble faire la rotation comme il l'a implémenté. Juste avec 40 ans de retard. Comme je l'ai mentionné dans ma réponse, c'est en fait une méthode très simple. Mentionné comme étant le choix uniquement lorsque la rotation rapide est disponible. Actuellement, je suis dans Haskell et il a une méthode intégrée pour faire un cycle de liste (disons tableau) indéfiniment (l'évaluation paresseuse fait une répétition infinie sans problème) et cela pourrait être utile. Pourtant, Haskell a déjà une permutationsfonction standard :)

Rédu

6

Une version inspirée de Haskell:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]

function perms(xs) {
  if (!xs.length) return [[]];
  return xs.flatMap((xi, i) => {
    // get permutations of xs without its i-th item, then prepend xi to each
    return perms([...xs.slice(0,i), ...xs.slice(i+1)]).map(xsi => [xi, ...xsi]);
  });
}
document.write(JSON.stringify(perms([1,2,3])));

Développer l'extrait

caub
la source

5

Répondez sans avoir besoin d'un tableau extérieur ou d'une fonction supplémentaire

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

Taylor Merlu
la source

pouvez-vous en faire une COmbination? stackoverflow.com/questions/53555563/…

Techdive

5

La version la plus rapide, la plus efficace et la plus élégante de nos jours (2020)

function getArrayMutations(arr, perms = [], len = arr.length) {
  if (len === 1) perms.push(arr.slice(0))

  for (let i = 0; i < len; i++) {
    getArrayMutations(arr, perms, len - 1)

    len % 2 // parity dependent adjacent elements swap
      ? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]]
      : [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]]
  }

  return perms
}

const arrayToMutate = [1, 2, 3, 4, 5, 6, 7, 8, 9]

const startTime = performance.now()
const arrayOfMutations = getArrayMutations(arrayToMutate)
const stopTime = performance.now()
const duration = (stopTime - startTime) / 1000

console.log(`${arrayOfMutations.length.toLocaleString('en-US')} permutations found in ${duration.toLocaleString('en-US')}s`)

Développer l'extrait

Vladislav Ladicky
la source

Salut, cela vous dérange-t-il d'expliquer ce que len % 2 // parity dependent adjacent elements swapsignifie et pourquoi est-il utilisé?

Pramesh Bajracharya le

Mon code utilise "l'algorithme du tas" pour générer les permutations de tableau. Donc, si vous voulez savoir comment mon code fonctionne sous le capot, lisez cette explication de l'algorithme de Heap: en.m.wikipedia.org/wiki/Heap%27s_algorithm

Vladislav Ladicky le

Avez-vous essayé d'imprimer le résultat? comment contrôler le maximum si les éléments du tableau sur 10?

Marvix le

4

Voici une solution cool

const rotations = ([l, ...ls], right=[]) =>
  l ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []

const permutations = ([x, ...xs]) =>
  x ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
  
console.log(permutations("cat"))

Développer l'extrait

Chris Vouga
la source

2

Voici une autre solution "plus récursive".

function perms(input) {
  var data = input.slice();
  var permutations = [];
  var n = data.length;

  if (n === 0) {
    return [
      []
    ];
  } else {
    var first = data.shift();
    var words = perms(data);
    words.forEach(function(word) {
      for (var i = 0; i < n; ++i) {
        var tmp = word.slice();
        tmp.splice(i, 0, first)
        permutations.push(tmp);
      }
    });
  }

  return permutations;
}

var str = 'ABC';
var chars = str.split('');
var result = perms(chars).map(function(p) {
  return p.join('');
});

console.log(result);

Développer l'extrait

Production:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]

schickling
la source

pouvez-vous faire une combinaison pour cela? stackoverflow.com/questions/53555563/…

Techdive

2

   function perm(xs) {
       return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
        for (var i = 0; i < xs.length; i++) {
          acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
        }
        return acc;
      }, []);
    }

Testez-le avec:

console.log(JSON.stringify(perm([1, 2, 3,4])));

eb58
la source

2

La plupart des autres réponses n'utilisent pas les nouvelles fonctions du générateur javascript qui est une solution parfaite à ce type de problème. Vous n'avez probablement besoin que d'une permutation à la fois en mémoire. De plus, je préfère générer une permutation d'une plage d'indices car cela me permet d'indexer chaque permutation et de passer directement à une permutation particulière ainsi que d'être utilisé pour permuter toute autre collection.

// ES6 generator version of python itertools [permutations and combinations]
const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; }
const isEmpty = arr => arr.length === 0;

const permutations = function*(a) {
    const r = arguments[1] || [];
    if (isEmpty(a)) yield r;
    for (let i of range(a.length)) {
        const aa = [...a];
        const rr = [...r, ...aa.splice(i, 1)];
        yield* permutations(aa, rr);
    }
}
console.log('permutations of ABC');
console.log(JSON.stringify([...permutations([...'ABC'])]));

const combinations = function*(a, count) {
    const r = arguments[2] || [];
    if (count) {
        count = count - 1;
        for (let i of range(a.length - count)) {
            const aa = a.slice(i);
            const rr = [...r, ...aa.splice(0, 1)];
            yield* combinations(aa, count, rr);
        }
    } else {
        yield r;
    }
}
console.log('combinations of 2 of ABC');
console.log(JSON.stringify([...combinations([...'ABC'], 2)]));



const permutator = function() {
    const range = function*(args) {
        let {begin = 0, count} = args;
        for (let i = begin; count; count--, i+=1) {
            yield i;
        }
    }
    const factorial = fact => fact ? fact * factorial(fact - 1) : 1;

    return {
        perm: function(n, permutationId) {
            const indexCount = factorial(n);
            permutationId = ((permutationId%indexCount)+indexCount)%indexCount;

            let permutation = [0];
            for (const choiceCount of range({begin: 2, count: n-1})) {
                const choice = permutationId % choiceCount;
                const lastIndex = permutation.length;

                permutation.push(choice);
                permutation = permutation.map((cv, i, orig) => 
                    (cv < choice || i == lastIndex) ? cv : cv + 1
                );

                permutationId = Math.floor(permutationId / choiceCount);
            }
            return permutation.reverse();
        },
        perms: function*(n) {
            for (let i of range({count: factorial(n)})) {
                yield this.perm(n, i);
            }
        }
    };
}();

console.log('indexing type permutator');
let i = 0;
for (let elem of permutator.perms(3)) {
  console.log(`${i}: ${elem}`);
  i+=1;
}
console.log();
console.log(`3: ${permutator.perm(3,3)}`);

Développer l'extrait

Doug Coburn
la source

2

#!/usr/bin/env node
"use strict";

function perm(arr) {
    if(arr.length<2) return [arr];
    var res = [];
    arr.forEach(function(x, i) {
        perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) {
            res.push([x].concat(a));
        });
    });
    return res;
}

console.log(perm([1,2,3,4]));

dashxdr
la source

2

En voici un que j'ai fait ...

const permute = (ar) =>
  ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
    {permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);

Et le voici encore mais écrit moins laconiquement! ...

function permute(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
      .map(value=>accumulator.push([].concat(inputArray[index],value)));
    return accumulator;
  },[]);
}

Comment cela fonctionne: Si le tableau est plus long qu'un élément, il parcourt chaque élément et le concatène avec un appel récursif à lui-même avec les éléments restants comme argument. Il ne mute pas le tableau d'origine.

Roger Heathcote
la source

2

Réponse fonctionnelle avec flatMap:

const getPermutationsFor = (arr, permutation = []) =>
  arr.length === 0
    ? [permutation]
    : arr.flatMap((item, i, arr) =>
        getPermutationsFor(
          arr.filter((_,j) => j !== i),
          [...permutation, item]
        )
      );

jabsatz
la source

1

"use strict";
function getPermutations(arrP) {
    var results = [];
    var arr = arrP;
    arr.unshift(null);
    var length = arr.length;

    while (arr[0] === null) {

        results.push(arr.slice(1).join(''));

        let less = null;
        let lessIndex = null;

        for (let i = length - 1; i > 0; i--) {
            if(arr[i - 1] < arr[i]){
                less = arr[i - 1];
                lessIndex = i - 1;
                break;
            }
        }

        for (let i = length - 1; i > lessIndex; i--) {
            if(arr[i] > less){
                arr[lessIndex] = arr[i];
                arr[i] = less;
                break;
            }
        }

        for(let i = lessIndex + 1; i<length; i++){
           for(let j = i + 1; j < length; j++){
               if(arr[i] > arr[j] ){
                   arr[i] = arr[i] + arr[j];
                   arr[j] = arr[i] - arr[j];
                   arr[i] = arr[i] - arr[j];
               }
           }
        }
    }

    return results;
}

var res = getPermutations([1,2,3,4,5]);
var out = document.getElementById('myTxtArr');
res.forEach(function(i){ out.value+=i+', '});

textarea{
   height:500px;
  width:500px;
}

<textarea id='myTxtArr'></textarea>

Développer l'extrait

Produit des permutations ordonnées lexicographiquement. Fonctionne uniquement avec des nombres. Dans les autres cas, vous devez changer la méthode de swap à la ligne 34.

tamaz bagdavadze
la source

1

Similaire dans l'esprit à la solution de style Haskell de @crl, mais fonctionnant avec reduce:

function permutations( base ) {
  if (base.length == 0) return [[]]
  return permutations( base.slice(1) ).reduce( function(acc,perm) {
    return acc.concat( base.map( function(e,pos) {
      var new_perm = perm.slice()
      new_perm.splice(pos,0,base[0])
      return new_perm
    }))
  },[])    
}

rplantiko
la source

1

C'est un très bon cas d'utilisation de map / reduction:

function permutations(arr) {
    return (arr.length === 1) ? arr :
    arr.reduce((acc, cv, index) => {
        let remaining = [...arr];
        remaining.splice(index, 1);
        return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
    }, []);
}

Tout d'abord, nous gérons le cas de base et renvoyons simplement le tableau s'il n'y a qu'un élément
Dans tous les autres cas
- nous créons un tableau vide
- boucle sur le tableau d'entrée
- et ajoutez un tableau de la valeur actuelle et toutes les permutations du tableau restant [].concat(cv,a)

danielbuechele
la source

1

Voici une version ES6 minimale. Les fonctions aplatir et sans fonctions peuvent être extraites de Lodash.

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));

Résultat:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Márton Sári
la source

1

perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]

eb58
la source

2

Pouvez-vous ajouter une explication s'il vous plaît.

Mehdi Bounya

3

Bien que cette réponse puisse résoudre la question, elle ne contient aucune explication sur comment ou pourquoi elle le fait.

samlev

1

const permutations = array => {
  let permut = [];
  helperFunction(0, array, permut);
  return permut;
};

const helperFunction = (i, array, permut) => {
  if (i === array.length - 1) {
    permut.push(array.slice());
  } else {
    for (let j = i; j < array.length; j++) {
      swapElements(i, j, array);
      helperFunction(i + 1, array, permut);
      swapElements(i, j, array);
    }
  }
};

function swapElements(a, b, array) {
  let temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

console.log(permutations([1, 2, 3]));

Développer l'extrait

ASHISH RANJAN
la source

1

Assez tard. Toujours juste au cas où cela aiderait quelqu'un.

function permute(arr) {
  if (arr.length == 1) return arr

  let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i + 1)])
                              .map(v => [d,v].join(''))).flat()

  return res
}

console.log(permute([1,2,3,4]))

Développer l'extrait

Nitish Narang
la source

1

J'ai eu une fissure à faire une version de ceci qui tente d'être une programmation concise mais lisible et purement fonctionnelle.

function stringPermutations ([...input]) {
  if (input.length === 1) return input;

  return input
    .map((thisChar, index) => {
      const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
      return stringPermutations(remainingChars)
        .map(remainder => thisChar + remainder);
    })
    .reduce((acc, cur) => [...acc, ...cur]);
}

Notez que la mise en forme de l'argument transforme une chaîne d'entrée en un tableau. Je ne sais pas si c'est un peu trop magique ... Je ne sais pas si je l'ai vu dans la nature. Pour une réelle lisibilité, je le ferais probablement plutôt input = [...input]pour la première ligne de la fonction.

Jameslol
la source

1

Il s'agit d'une implémentation de l'algorithme de Heap (similaire à @ le_m), sauf qu'il est récursif.

function permute_kingzee(arr,n=arr.length,out=[]) {
    if(n == 1) {
        return out.push(arr.slice());
    } else {
        for(let i=0; i<n; i++) {
            permute_kingzee(arr,n-1, out);
            let j = ( n % 2 == 0 ) ? i : 0;
            let t = arr[n-1];
            arr[n-1] = arr[j];
            arr[j] = t;
        }
        return out;
    }
}

On dirait que c'est aussi assez rapide: https://jsfiddle.net/3brqzaLe/

Zee
la source

1

Ma première contribution au site. De plus, d'après les tests que j'ai effectués, ce code tourne plus vite que toutes les autres méthodes mentionnées ici avant cette date, bien sûr il est minime s'il y a peu de valeurs, mais le temps augmente de façon exponentielle lorsqu'on en ajoute trop.

function permutations(arr) {
    var finalArr = [];
    function iterator(arrayTaken, tree) {
        var temp;
        for (var i = 0; i < tree; i++) {
            temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else {
                iterator(temp, tree + 1);
            }
        }
    }
    iterator(arr, 1);
    return finalArr;
};

Urielzen
la source

J'ai ajouté une comparaison de performances stackoverflow.com/a/37580979/1647737 - n'hésitez pas à mettre à jour.

le_m

0

J'ai écrit un article pour montrer comment permuter un tableau en JavaScript. Voici le code qui fait cela.

var count=0;
function permute(pre,cur){ 
    var len=cur.length;
    for(var i=0;i<len;i++){
        var p=clone(pre);
        var c=clone(cur);
        p.push(cur[i]);
        remove(c,cur[i]);
        if(len>1){
            permute(p,c);
        }else{
            print(p);
            count++;
        }
    }
}
function print(arr){
    var len=arr.length;
    for(var i=0;i<len;i++){
        document.write(arr[i]+" ");
    }
    document.write("<br />");
}
function remove(arr,item){
    if(contains(arr,item)){
        var len=arr.length;
        for(var i = len-1; i >= 0; i--){ // STEP 1
            if(arr[i] == item){             // STEP 2
                arr.splice(i,1);              // STEP 3
            }
        }
    }
}
function contains(arr,value){
    for(var i=0;i<arr.length;i++){
        if(arr[i]==value){
            return true;
        }
    }
    return false;
}
function clone(arr){
    var a=new Array();
    var len=arr.length;
    for(var i=0;i<len;i++){
        a.push(arr[i]);
    }
    return a;
}

Il suffit d'appeler

permute ([], [1,2,3,4])

marchera. Pour plus de détails sur la façon dont cela fonctionne, veuillez vous référer à l'explication dans ce post.

PixelsTech
la source

0

function nPr(xs, r) {
    if (!r) return [];
    return xs.reduce(function(memo, cur, i) {
        var others  = xs.slice(0,i).concat(xs.slice(i+1)),
            perms   = nPr(others, r-1),
            newElms = !perms.length ? [[cur]] :
                      perms.map(function(perm) { return [cur].concat(perm) });
        return memo.concat(newElms);
    }, []);
}

Jonas
la source

Permutations en JavaScript?

Réponses:

Comparaison des performances

Voici une solution cool