Obtenez toutes les permutations possibles possibles

Pour un petit tableau, vous pouvez utiliser l'un des algorithmes référencés, mapper chaque permutation à une chaîne et lancer l'ensemble du tableau dans un Ensemble pour supprimer les doublons. Quelque chose comme:

 let a = ['^','^','>','>','+','<','<']; let ps = permutations(a); // return value should be array of arrays. let qs = ps.map(p => p.join("")); let s = new Set(qs); 

Cela devrait fonctionner correctement pour les tableaux avec < 10 symboles.

Sinon, voir ici et ici pour une variété d'approches que vous pouvez traduire en JavaScript.

Une méthode populaire est l' algorithme de Pandita qui énumère les permutations dans l'ordre lexicographique en utilisant une règle de succession, générant uniquement des permutations "uniques". Une brève explication de cette approche est donnée ici et ici . Voici une implémentation JavaScript (ES6):

 function swap(a, i, j) { const t = a[i]; a[i] = a[j]; a[j] = t; } function reverseSuffix(a, start) { if (start === 0) { a.reverse(); } else { let left = start; let right = a.length - 1; while (left < right) swap(a, left++, right--); } } function nextPermutation(a) { // 1. find the largest index `i` such that a[i] < a[i + 1]. // 2. find the largest `j` (> i) such that a[i] < a[j]. // 3. swap a[i] with a[j]. // 4. reverse the suffix of `a` starting at index (i + 1). // // For a more intuitive description of this algorithm, see: // https://www.nayuki.io/page/next-lexicographical-permutation-algorithm const reversedIndices = [...Array(a.length).keys()].reverse(); // Step #1; (note: `.slice(1)` maybe not necessary in JS?) const i = reversedIndices.slice(1).find(i => a[i] < a[i + 1]); if (i === undefined) { a.reverse(); return false; } // Steps #2-4 const j = reversedIndices.find(j => a[i] < a[j]); swap(a, i, j); reverseSuffix(a, i + 1); return true; } function* uniquePermutations(a) { const b = a.slice().sort(); do { yield b.slice(); } while (nextPermutation(b)); } let a = ['^','^','>','>','+','<','<']; let ps = Array.from(uniquePermutations(a)); let qs = ps.map(p => p.join("")); console.log(ps.length); console.log(new Set(qs).size); 

La fonction nextPermutation transforme un tableau en place soit dans le successeur lexicographique, soit le minimum léxicographique si le tableau est déjà le maximum lexicographique. Dans le premier cas, il renvoie true , sinon false . Cela vous permet de parcourir toutes les permutations à partir du tableau minimum (trié) jusqu'à nextPermutation que nextPermutation roule et renvoie false .

Eh bien, le problème des résultats uniques sera évidemment un tueur d'efficacité, car il faudra vérifier la liste des résultats chaque fois que vous créez une nouvelle permutation. En ce qui concerne l'algorithme, il fonctionnera essentiellement de la même manière que les autres algorithmes de permutation, mais vos critères de suppression des doublons impliqueront beaucoup plus de chèques. Si la taille du tableau est une faible efficacité, cela ne devrait pas être une grande préoccupation. Il suffit simplement de parcourir le réseau de réponses si la valeur déjà trouvée n'ajoute pas au tableau. Une façon d'accélérer ce processus de vérification est de déterminer une manière de trier le tableau des réponses. Par exemple, ^ vient toujours avant * qui vient après (alors il n'est pas nécessaire de vérifier l'ensemble du tableau à chaque fois. Il existe d'autres méthodes pour accélérer cela, mais à la fin de la journée, il est encore une exigence assez coûteuse. Le tableau est petit, il ne devrait pas être important du tout, sauf si vous prévoyez de faire cette permutation.