Mélanger un tableau autant que possible

La première chose à noter est que le nombre de permutations augmente très rapidement en ce qui concerne le nombre d'éléments (13 éléments = 6 permutations de bilan), de sorte que tout type d'algorithme qui les génère se détériore en performances pour un tableau d'entrée suffisamment important.

La deuxième chose à noter est que puisque le nombre de permutations est très important, il est coûteux de les stocker en mémoire, donc vous êtes mieux d'utiliser un générateur pour vos permutations et de faire des choses avec elles au fur et à mesure qu'elles sont générées.

La troisième chose à noter est que les algorithmes récursifs apportent une grande surcharge, donc même si vous trouvez une solution récursive, vous devriez vous efforcer d'obtenir une solution non récursive. L'obtention d'une solution non récursive si une récursive existe est toujours possible, mais elle peut augmenter la complexité du code.

J'ai écrit une implémentation non récursive pour vous, basée sur l'algorithme Steinhaus-Johnson-Trotter ( http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm )

 function swap(arr, a,b){ var temp = arr[a]; arr[a]=arr[b]; arr[b]=temp; } function factorial(n) { var val = 1; for (var i=1; i<n; i++) { val *= i; } return val; } function permute(perm, func){ var total = factorial(perm.length); for (var j=0, i=0, inc=1; j<total; j++, inc*=-1, i+=inc) { for (; i<perm.length-1 && i>=0; i+=inc) { func.call(perm); swap (perm, i, i+1); } func.call(perm); if (inc === 1) { swap(perm, 0,1); } else { swap(perm, perm.length-1, perm.length-2); } } } console.clear(); count = 0; permute([1,2,3,4,5,6], function(){console.log(this); count++;}); console.log('There have been ' + count + ' permutations'); 

http://jsbin.com/eXefawe/2/edit

Essayez une approche récursive. Voici un indice: chaque permutation de [0,2,3] est soit

• [0] plus une permutation de [2,3] ou
• [2] plus une permutation de [0,3] ou
• [3] plus une permutation de [0,2]

Comme l'a indiqué le zodiaque, la meilleure solution à ce problème est récursive:

 var permute = (function () { return permute; function permute(list) { return list.length ? list.reduce(permutate, []) : [[]]; } function permutate(permutations, item, index, list) { return permutations.concat(permute( list.slice(0, index).concat( list.slice(index + 1))) .map(concat, [item])); } function concat(list) { return this.concat(list); } }()); alert(JSON.stringify(permute([1,2,3]))); 

Toutes les permutations d'un ensemble peuvent être trouvées en sélectionnant un élément dans l'ensemble et en permutant récursivement (réarrangant) les éléments restants. L' approche Backtracking peut être utilisée pour trouver la solution.

Étapes d'algorithme ( source ):

Pseudocode ( source ):

 permute(i) if i == N output A[N] else for j = i to N do swap(A[i], A[j]) permute(i+1) swap(A[i], A[j]) 

Mise en œuvre Javascript ( jsFiddle ):

 Array.prototype.clone = function () { return this.slice(0); }; var input = [1, 2, 3, 4]; var output = []; function permute(i) { if (i == input.length) output.push(input.clone()); else { for (var j = i; j < input.length; j++) { swap(i, j); permute(i + 1); swap(i, j); // backtrack } } }; function swap(i, j) { var temp = input[i]; input[i] = input[j]; input[j] = temp; } permute(0); console.log(output); 

Pour un ensemble de longueur n, nous pouvons précomputer le nombre de permutations possibles. C'est n! (N factoriel)

 function factorial(n){ return n<=0?1:n*factorial(n-1);} //There are better ways, but just for illustration's sake 

Et, nous pouvons créer une fonction qui mappe un entier P entre 0 … n! -1 et une permutation distincte.

 function map(p,orgArr){ var tempArr=orgArr.slice(); //Create a copy var l=orgArr.length; var permArr=[]; var pick; do{ pick=p%l; //mod operator permArr.push(tempArr.splice(pick,1)[0]); //Remove item number pick from the old array and onto the new p=(p-pick)/l; l--; }while(l>=1) return permArr; } 

À ce stade, tout ce que vous devez faire est de créer une ordering=[0,1,2,3,...,factorial(n)-1] tableau ordering=[0,1,2,3,...,factorial(n)-1] et de mélanger cela. Ensuite, vous pouvez faire une boucle for(var i=0;i<=ordering.length;i++) doSomething(map(ordering[i],YourArray));

Cela laisse simplement la question de la façon de mélanger le tableau de commande. Je crois que cela est bien documenté et en dehors de la portée de votre question puisque la réponse dépend de votre application (c'est-à-dire pseudo-aléatoire assez bien ou avez-vous besoin de la puissance cryptographique, de la vitesse souhaitée, etc.). Voir Comment aléatoirement (shuffle) un tableau JavaScript? et plein d'autres.

Ou bien, si le nombre de permutations est tellement important que vous ne voulez pas créer cet énorme tableau de commande, il vous suffit de sélectionner distinctement les valeurs de i pour la boucle ci-dessus entre 0-n! -1. Si l'uniformité est nécessaire, plutôt que le hasard, une façon simple serait d'utiliser des racines primitives: http://en.wikipedia.org/wiki/Primitive_root_modulo_n

Vous n'avez pas besoin de vous guider. La démo devrait rendre le schéma assez clair: http://jsfiddle.net/BGYk4/

 function shuffle(arr) { var output = []; var n = arr.length; var ways = []; for(var i = 0, j = 1; i < n; ways.push(j *= ++i)); var totalWays = ways.pop(); for(var i = 0; i < totalWays; i++) { var copy = arr.slice(); output[i] = []; for(var k = ways.length - 1; k >= 0; k--) { var c = Math.floor(i/ways[k]) % (k + 2); output[i].push(copy.splice(c,1)[0]); } output[i].push(copy[0]); } return output; } 

Cela devrait générer tous les "shuffles" possibles

 console.log(shuffle(['a', 'b', 'c', 'd', 'e'])); 

Celui-ci est plus mignon (mais la sortie de l'autre exemple est beaucoup plus claire): http://jsfiddle.net/wCnLf/

 function shuffle(list) { var shufflings = []; while(true) { var clone = list.slice(); var shuffling = []; var period = 1; while(clone.length) { var index = Math.floor(shufflings.length / period) % clone.length; period *= clone.length; shuffling.push(clone.splice(index,1)[0]); } shufflings.push(shuffling); if(shufflings.length == period) return shufflings; } } 

Et bien sûr, il produit toujours tous les "mélanges" possibles

 console.log(shuffle(['a', 'b', 'c', 'd', 'e'])); 

L' exemple de tibos ci-dessus était exactement ce que je cherchais mais j'ai eu du mal à le faire fonctionner, j'ai fait une autre solution en tant que module npm:

 var generator = new Permutation([1, 2, 3]); while (generator.hasNext()) { snippet.log(generator.next()); } 

 <script src="http://tjcrowder.github.io/simple-snippets-console/snippet.js"></script> <script src="http://rawgit.com/bcard/iterative-permutation/master/iterative-permutation.js"></script>