Permutations in JavaScript

Permutations in JavaScript?

If you notice, the code actually splits the chars into an array prior to do any permutation, so you simply remove the join and split operation

var permArr = [],

  usedChars = [];

function permute(input) {

  var i, ch;

  for (i = 0; i < input.length; i++) {

    ch = input.splice(i, 1)[0];

    usedChars.push(ch);

    if (input.length == 0) {

      permArr.push(usedChars.slice());

    }

    permute(input);

    input.splice(i, 0, ch);

    usedChars.pop();

  }

  return permArr

};

document.write(JSON.stringify(permute([5, 3, 7, 1])));

permutations of objects in javascript

This is similar to a normal combination function but a little easier since you can go through the levels on at a time.

Here's a simple recursive approach:

let arr = [ 

    { ent: 'animal', vals: [ 'dog', 'cat' ] },

    { ent: 'color', vals: [ 'red', 'blue', 'green' ] },

    { ent: 'owner', vals: [ 'bob', 'david' ] } 

  ]

function getCombinations(arr){

    if (arr.length === 0) return [[]]

    let [current, ...rest] = arr

    let combinations = getCombinations(rest)

    return current.vals.reduce((a, string) => 

        [ ...a, ...combinations.map(c => [string, ...c])], [])

}

let c = getCombinations(arr)

console.log(c)

Subset of permutations in JavaScript with up to~6 duplicates per element

I don't know if that's 10,000 instances of one element, and then the rest are individually unique elements or at least K of each unique element. Because of that I can't just fed them into a Set, and there maybe fewer than K of one element so I can't just create a new input by duplicating the new ones K times

So just group and count them. Seems simple enough:

function subsetPermutations(arr, size) {
    const counts = {};
    for (const el of arr) {
        counts[el] = (counts[el] ?? 0) + 1;
    }
    const unique = Object.keys(counts);
    const result = Array.from({length: size});
    function* recurse(depth) {
        if (depth == size) {
            yield result;
        } else {
            for (const el of unique) {
                if (counts[el]) {
                    result[depth] = el;
                    counts[el]--;
                    yield* recurse(depth+1)
                    counts[el]++;
                }
            }
        }
    }
    return recurse(0);
}

for (const perm of subsetPermutations(["a", "b", "b", "c", "c", "c"], 3)) {
    console.log(perm.join('-'));
}

JavaScript - Generating all permutations of an array

Not sure if this is the best way, but it seems to work.

@Nina's solution looks good, but it does a fair bit of array concat & slice, so this might work better for larger sets as it avoids that. I do use an object for duplicate checking, but hashmaps are super fast in JS.

Just curious, so did a performance test.
Doing [1,2,3,4,5,6,7], using @Nina's solution take's 38.8 seconds,.
Doing mine toke 175ms.. So the array concat / slice is a massive performance hit, and the marked duplicate will have the same issue. Just something to be aware off.

var ar1 = [2, 5];

var ar2 = [1, 2, 3];

function combo(c) {

  var r = [],

      len = c.length;

      tmp = [];

  function nodup() {

    var got = {};

    for (var l = 0; l < tmp.length; l++) {

      if (got[tmp[l]]) return false;

      got[tmp[l]] = true;

    }

    return true;

  }

  function iter(col,done) {    

    var l, rr;

    if (col === len) {      

      if (nodup()) {

        rr = [];

        for (l = 0; l < tmp.length; l++) 

          rr.push(c[tmp[l]]);        

        r.push(rr);

      }

    } else {

      for (l = 0; l < len; l ++) {            

        tmp[col] = l;

        iter(col +1);

      }

    }

  }

  iter(0);

  return r;

}

console.log(JSON.stringify(combo(ar1)));

console.log(JSON.stringify(combo(ar2)));

console.log('something bigger [1,2,3,4,5,6,7]');

console.time('t1');

combo([1,2,3,4,5,6,7]);

console.timeEnd('t1');

How do array permutation splitting by (n)

You can try this one:

Script:

function test() {
  var array = [1, 4, 5, 8];

  console.log(getCombinations(array, 3)) 
}

function getCombinations(chars, len) {
  var result = [];
  var f = function(prefix, chars) {
    for (var i = 0; i < chars.length; i++) {
      var elem = [...prefix, chars[i]];
      if(elem.length == len)
        result.push(elem);
      f(elem, chars.slice(i + 1));
    }
  }
  f([], chars);
  return result;
}

Output:

output

Finding all permutations of array elements as concatenated strings

Heap's algorithm can be used to generate all permutations (without repetitions) of array elements, you can then use those permutations with array.join("") to convert them to strings. This works for arrays of any size and any type:

Here is a quick javascript implementation:

// some global variable to store the results
var result = []

// currentSize should be invoked with the array size
function permutation(arr, currentSize) {
    if (currentSize == 1) { // recursion base-case (end)
        result.push(arr.join(""));
        return;
    }
    
    for (let i = 0; i < currentSize; i++){
        permutation(arr, currentSize - 1);
        if (currentSize % 2 == 1) {
            let temp = arr[0];
            arr[0] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        } else {
            let temp = arr[i];
            arr[i] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        }
    }
}

let array = ["1","2","3","4"];
permutation(array, array.length);

console.log(result);
// use result here

Keep in mind that this is very computationally expensive, with complexity of O(n!).

Unique permutations with repeating elements in JavaScript

After having an equality criteria between the different permutations, we need to establish a canonical form for each pattern (equality class). We will then try to only generate those.

In your case, where order of 1s, 2s and 3s does not matter, we could decide that their respective first occurrences must be in the order 123, and 2 cannot appear without 1 and 3 not without 2. So whether the pattern is aabcbc, aacbcb, bbacac, …, or ccbaba, the only form that we want to generate is 112323. Or when the pattern is aaa/bbb/ccc we only generate 111 but not 222 or 333.

We can then write an algorithm which follows these rules for canonical forms:

function patterns(values, len) {
    function* recurse(list, used, depth) {
        if (depth == len) {
            yield list.slice();
        } else {
            for (let j=0; j<used; j++) { // only put already used values at this position
                list[depth] = values[j];
                yield* recurse(list, used, depth+1);
            }
            if (used < values.length) { // or the single next unused value
                list[depth] = values[used];
                yield* recurse(list, used+1, depth+1); // which is counted as used here
            }
        }
    }
    return recurse([], 0, 0);
}

This simply generates all combinations of a certain length from the distinct values, but you can use the same approach in your algorithm that generates permutations from a certain amount of non-unique values. It does get a bit more complicated though: the canonical form 121 cannot be achieved if we only have the values 122 available, but the pattern 212 still should be generated. We need to adjust our rule so that the ordering requirement is only amongst elements of the same number of occurrences. So we have to keep different used counts for them.

function permutationPatterns(elements) {
    const len = elements.length;
    const unique = new Map(elements.map(el => [el, {value: el, occurrences: 0}]));
    let max = 0;
    for (const el of elements) {
        const o = unique.get(el);
        max = Math.max(max, ++o.occurrences);
    }
    const byOccurrences = Array.from({length: max+1}, () => ({elements: [], used: 0}));
    for (const o of unique.values()) {
        byOccurrences[o.occurrences].elements.push(o);
    }

    function* generate(list, depth) {
        if (depth == len) {
            yield list.slice();
        } else {
            for (const options of byOccurrences) {
                options.used++;
                for (const option of options.elements.slice(0, options.used)) {
                    if (option.occurrences == 0) continue;
                    option.occurrences--;
                    list[depth] = option.value;
                    yield* generate(list, depth+1);
                    option.occurrences++;
                }
                options.used--;
            }
        }
    }
    return generate([], 0);
}

Get all the possible unique permutations

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.

Permutations in JavaScript