Javascript: Given an array, return a number of arrays with different ordered combinations of elements

Question

I need code that takes an array, counts the number of elements in it and returns a set of arrays, each displaying a different combination of elements. However, the starting element should be the same for each array. Better to explain with a few examples:

var OriginalArray = ['a','b','c']

should return

results: [['a','b','c'], ['a','c','b']]

or for example:

var originalArray = ['a','b','c','d']

should return

[['a','b','c','d'], ['a','b','d', 'c'], ['acbd', 'acdb', 'adbc', 'adcb']]

Again note how the starting element, in this case 'a' should always be the starting element.

remove the first element, compute [permutations](http://stackoverflow.com/questions/34013675/permutations-without-recursive-function-call) of the rest and append the first element to each one. — georg, Dec 21 '16 at 14:35
Is this how result for second example should look like `[["a","b","c","d"],["a","c","b","d"],["a","d","c","b"],["a","c","d","b"],["a","d","b","c"],["a","b","d","c"]]`? — Nenad Vracar, Dec 21 '16 at 14:53

score 0 · Answer 1 · answered Dec 21 '16 at 15:05

You can use Heap's algorithm for permutations and modify it a bit to add to result only if first element is equal to first element of original array.

var arr = ['a', 'b', 'c', 'd']

function generate(data) {
  var r = [];
  var first = data[0];

  function swap(x, y) {
    var tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
  }

  function permute(n) {
    if (n == 1 && data[0] == first) r.push([].concat(data));
    else {
      for (var i = 0; i < n; i++) {
        permute(n - 1);
        swap(n % 2 ? 0 : i, n - 1);
      }
    }
  }
  permute(data.length);
  return r;
}

console.log(generate(arr))

score 0 · Answer 2 · answered Dec 21 '16 at 16:52

You have to do a .slice(1) to feed the rest of the array to a permutations function. Then you can use .map() to stick the first item to the front of each array in the result of permutations function.

If you will do this job on large sets and frequently then the performance of the permutations function is important. The following uses a dynamical programming approach and to my knowledge it's the fastest.

function perm(a){
  var r = [[a[0]]],
      t = [],
      s = [];
  if (a.length <= 1) return a;
  for (var i = 1, la = a.length; i < la; i++){
    for (var j = 0, lr = r.length; j < lr; j++){
      r[j].push(a[i]);
      t.push(r[j]);
      for(var k = 1, lrj = r[j].length; k < lrj; k++){
        for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
        t[t.length] = s;
        s = [];
      }
    }
    r = t;
    t = [];
  }
  return r;
}

var arr = ['a','b','c','d'],
 result = perm(arr.slice(1)).map(e => [arr[0]].concat(e));
console.log(JSON.stringify(result));

Javascript: Given an array, return a number of arrays with different ordered combinations of elements

2 Answers2