Theodore K. - 1 year ago 83
Javascript Question

# Get all the possible unique permutations

Having a small array with some symbols like

`['^','^','>','>','+','<','<']`
, how can I get all the different permutations? I know that similar questions have been asked (and already have some excellent answers) like:

however they don't present unique results. How can I efficiently get each possible outcome only once?

For a small array, you can use one of the referenced algorithms, map each permutation to a string, and throw the whole array into a Set to discard duplicates. Something like:

``````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);
``````

This should work fine for arrays with `< 10` symbols.

Otherwise, see here and here for a variety of approaches that you can translate to JavaScript.

One popular method is the Pandita algorithm which enumerates permutations in lexicographic order using a succession rule, effectively only generating "unique" permutations. An short explanation of this approach is given here and here. Here's a JavaScript (ES6) implementation:

``````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);
``````

The `nextPermutation` function transforms an array in-place into either the lexicographic successor, or the lexicographic minimum if the array is already the lexicographic maximum. In the first case, it returns `true`, otherwise `false`. This allows you to cycle through all the permutations starting from the minimum (sorted) array until `nextPermutation` rolls over and returns `false`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download