Theodore K. - 1 year ago 66

Javascript Question

Having a **small** array with some symbols like

`['^','^','>','>','+','<','<']`

however they don't present

Answer Source

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`

.