javascript - Get all the possible unique permutations

Question

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:

• Shuffle an array as many as possible
• Permutations in JavaScript?

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

Answer 1

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.