2

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?

Community
  • 1
  • 1
Theodore K.
  • 5,058
  • 4
  • 30
  • 46
  • You should use one of those solutions, but add each result to a map as its generated, and only add it to the arr if its not already in the map – William B Oct 26 '16 at 14:04
  • You should clarify whether you want *permutations* or (as I suspect) you actually want *combinations* http://www.math.uiuc.edu/~wgreen4/Math124S07/PermuCombinations.pdf – Bradley Thomas Oct 26 '16 at 22:13
  • @Brad Thomas. I suspect that the right term is "Combinations without Repetition" but I'm not sure, the examples that I find are with different numbers/symbols while my array has duplicates. – Theodore K. Oct 27 '16 at 06:47

2 Answers2

4

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.

Community
  • 1
  • 1
0

Well the unique results issue is obviously going to be an efficiency killer as you going to have to check the results list each time you create a new permutation. As for the algorithm it will work in basically the same way as the other permutation algorithms, but your remove duplicates criteria will involve many more checks. If the size of the array is small efficiency should not be a large concern. Simply just loop through the answer array if value already found do not add to array. A way to speed up this checking process is to determine a way of sorting the answers array. For example ^ always comes before * which comes after ( Then you don't have to check the entire array each time. There are other methods of speeding this up but at the end of the day its still a pretty computationally expensive requirement. Since your array is small it should not matter at all unless you plan on doing this permutation ALOT

MikeB0317
  • 1
  • 1