CODEWITHSUNDEEP
javascriptarraysalgorithmsortingcombinations
Vorenus
Vorenus

Reputation: 83

Derive every possible combination of elements in array

Given an array and a length, I want to derive every possible combination of elements (non-repeating) at the specific length.

So given an array of:

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

and a length of 3, I'm after a function that outputs a 2-dimensional array as follows:

result = [
    ['a','b','c'],
    ['b','c','a'],
    ['c','a','b'],
    . . . etc.
]

I've tried tackling this and have had a deal of difficulty.

Upvotes: 0

Views: 354

Answers (1)

Michael Laszlo
Michael Laszlo

Reputation: 12239

The following code uses a brute-force approach. It generates every permutation of every combination of the desired length. Permutations are checked against a dictionary to avoid repeating them in the result.

function makePermutations(data, length) {
  var current = new Array(length), used = new Array(length),
      seen = {}, result = [];
  function permute(pos) {
    if (pos == length) {      // Do we have a complete combination?
      if (!seen[current]) {   // Check whether we've seen it before.
        seen[current] = true; // If not, save it.
        result.push(current.slice());
      }
      return;
    }
    for (var i = 0; i < data.length; ++i) {
      if (!used[i]) {         // Have we used this element before?
        used[i] = true;       // If not, insert it and recurse.
        current[pos] = data[i];
        permute(pos+1);
        used[i] = false;      // Reset after the recursive call.
      }
    }
  }
  permute(0);
  return result;
}

var permutations = makePermutations(['a', 'a', 'b', 'b'], 3);
for (var i = 0; i < permutations.length; ++i) {
  document.write('['+permutations[i].join(', ')+']<br />');
}

Upvotes: 1

Related Questions