How to get all possible combinations of elements in an array including order and lengths

Question

function getAllCombinations(arr) {

  var f = function(arr) {
    var result = [];
    var temp = [];

    for (var i = 0; i < arr.length; i++) {
      temp = [];
      temp.push(arr[i]);
      result.push(temp);

      for (var j = 0; j < arr.length; j++) {
        if (j != i) {
          temp = [];
          temp.push(arr[i]);
          temp.push(arr[j]);
          result.push(temp);

          for (var k = 0; k < arr.length; k++) {
            if (k != i && k != j) {
              temp = [];
              temp.push(arr[i]);
              temp.push(arr[j]);
              temp.push(arr[k]);
              result.push(temp);

              for (var l = 0; l < arr.length; l++) {
                if (l != i && l != j && l != k) {
                  temp = [];
                  temp.push(arr[i]);
                  temp.push(arr[j]);
                  temp.push(arr[k]);
                  temp.push(arr[l]);
                  result.push(temp);
                }
              }
            }
          }
        }
      }
    }

    return result;
  }
  return f(arr);
}

//call this function
console.log(getAllCombinations(["a", "b", "c", "d"]));

[["a"],["a","b"],["a","b","c"],["a","b","c","d"],["a","b","d"],["a","b","d","c"],["a","c"],["a","c","b"],["a","c","b","d"],["a","c","d"],["a","c","d","b"],["a","d"],["a","d","b"],["a","d","b","c"],["a","d","c"],["a","d","c","b"],["b"],["b","a"],["b","a","c"],["b","a","c","d"],["b","a","d"],["b","a","d","c"],["b","c"],["b","c","a"],["b","c","a","d"],["b","c","d"],["b","c","d","a"],["b","d"],["b","d","a"],["b","d","a","c"],["b","d","c"],["b","d","c","a"],["c"],["c","a"],["c","a","b"],["c","a","b","d"],["c","a","d"],["c","a","d","b"],["c","b"],["c","b","a"],["c","b","a","d"],["c","b","d"],["c","b","d","a"],["c","d"],["c","d","a"],["c","d","a","b"],["c","d","b"],["c","d","b","a"],["d"],["d","a"],["d","a","b"],["d","a","b","c"],["d","a","c"],["d","a","c","b"],["d","b"],["d","b","a"],["d","b","a","c"],["d","b","c"],["d","b","c","a"],["d","c"],["d","c","a"],["d","c","a","b"],["d","c","b"],["d","c","b","a"]]

A total of 64 combinations for a 4 length array.

The function works fine but I need to make this function recursive. The for loops have to be nested based on the length of the array and the push also increased per nested loop.

Really appreciate some advice.

Possible duplicate of [Cartesian product of multiple arrays in JavaScript](http://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) — Christopher Moore, Mar 03 '17 at 16:51
Hi @ChristopherMoore, I am getting a total of 64 combinations for a 4 length array. As shown i my above code the number of nested for loops is 4 and the number of push increased in each loop. This is the pattern i am looking forward to automate with a recursive function. The number of nested for loops = length of data array The conditions added in each nested loop changes = 1 The number of push increased per nested loop = 1 — Jeetu, Mar 07 '17 at 09:13
It's an interesting problem, and one that is unfortunately non trivial. The question I linked to above may not solve this exact problem, but the answers will definitely help guide you to figure out a recursive solution. — Christopher Moore, Mar 07 '17 at 09:36

Jeetu · Accepted Answer · 2017-03-14T16:47:29.467

Finally made it recursive !! Tried to work down on the the original code posted above moving each loop functionality into simple functions.

function getAllCombinations(inputArray) {
  var resultArray = [];
  var combine = function() {
    for (var i in inputArray) {
      var temp = [];
      var tempResult = [];
      for (var j in arguments) {
        tempResult.push(inputArray[arguments[j]]);
        if (arguments[j] == i) {
          temp = false;
        } else if (temp) {
          temp.push(arguments[j]);
        }
      }
      if (temp) {
        temp.push(i);
        combine.apply(null, temp);
      }
    }
    if (tempResult.length > 0) {
      resultArray.push(tempResult);
    }
    return resultArray;
  };
  return combine();
}

See the older version here.

Result produces 64 unique combinations for a 4 dimensional array

console.log(getAllCombinations(["a", "b", "c", "d"]));

[["a","b","c","d"],["a","b","c"],["a","b","d","c"],["a","b","d"],["a","b"],["a","c","b","d"],["a","c","b"],["a","c","d","b"],["a","c","d"],["a","c"],["a","d","b","c"],["a","d","b"],["a","d","c","b"],["a","d","c"],["a","d"],["a"],["b","a","c","d"],["b","a","c"],["b","a","d","c"],["b","a","d"],["b","a"],["b","c","a","d"],["b","c","a"],["b","c","d","a"],["b","c","d"],["b","c"],["b","d","a","c"],["b","d","a"],["b","d","c","a"],["b","d","c"],["b","d"],["b"],["c","a","b","d"],["c","a","b"],["c","a","d","b"],["c","a","d"],["c","a"],["c","b","a","d"],["c","b","a"],["c","b","d","a"],["c","b","d"],["c","b"],["c","d","a","b"],["c","d","a"],["c","d","b","a"],["c","d","b"],["c","d"],["c"],["d","a","b","c"],["d","a","b"],["d","a","c","b"],["d","a","c"],["d","a"],["d","b","a","c"],["d","b","a"],["d","b","c","a"],["d","b","c"],["d","b"],["d","c","a","b"],["d","c","a"],["d","c","b","a"],["d","c","b"],["d","c"],["d"]]

Matt Fernandez · Answer 2 · 2017-03-07T23:07:00.220

0

Here is my solution using a subroutine, and closures. Also slice is very useful here.

If you found this helpful, or if you think other people will find this helpful, don't be afraid to upvote.

function getMyCombinations(coll) {
  const result = [];
  
  (function search(currentPerm, letters) { 
    if (letters.length === 0) return result.push(currentPerm);
    let trimArray = letters.slice(1);
    letters.forEach(letter => search(currentPerm + letter, trimArray));
  })('', coll)

  return result;  
}


console.log(getMyCombinations(["a", "b", "c", "d"]));

I have refactored my original answer to better align with the users request.

function findPerm(array, currentPerm = '', result =[]) {
  if (array.length === 0) return result;
  let trimArray = array.slice(1);
  array.forEach(v => {
    let copy = [...result];
    let perm = (currentPerm + v).split('');
    let res = copy.push(perm);
    result = findPerm(trimArray, currentPerm + v, copy);
  });
  return result;
};

console.log(findPerm(['a', 'b', 'c', 'd']));

edited Mar 07 '17 at 23:07

answered Mar 04 '17 at 00:50

Matt Fernandez

190
6

This doesn't seem to produce the desired array that @Jeetu is after – Christopher Moore Mar 04 '17 at 11:14
Hi @ChristopherMoore, I am getting a total of 64 combinations for a 4 length array. As shown i my above code the number of nested for loops is 4 and the number of push increased in each loop. This is the pattern i am looking forward to automate with a recursive function. The number of nested for loops = length of data array The conditions added in each nested loop changes = 1 The number of push increased per nested loop = 1 – Jeetu Mar 07 '17 at 09:08
Hi @MattFernandez, The result produces 64 elements. There is duplication of items ( ["d","d","d"],["d","d","d","d"] ...) I only need unique items (any order / any length). The code I have posted above produces only unique items per combination. – Jeetu Mar 08 '17 at 12:34
That is very interesting. My apologies. – Matt Fernandez Mar 08 '17 at 15:58

score 0 · Answer 3 · answered Mar 14 '17 at 15:21

An alternative solution, seems getting the desired output :)

console.log(JSON.stringify(getMyCombinations(["a", "b", "c", "d"])))

function getMyCombinations(arry) {
    var len = arry.length;
    var tempArray = [];
    var result = []
    var tempCount = 1;

    var createCombinations = function(count){
        var singleLevelArray = [];

        arry.forEach(function(item){

            if(count){//1
                if(count > 1){
                    for(var j = 0; j < tempArray.length; j++){
                        if(tempArray[j].indexOf(item) === -1){
                            var x = tempArray[j].slice();
                            x.push(item);
                            singleLevelArray.push(x);
                            result.push(x);
                        }
                    } 
                } else {
                    for(var k = 0; k < len; k++){
                        if(item.indexOf(arry[k]) === -1){
                            tempArray.push([item, arry[k]]);
                            result.push([item, arry[k]]);
                        }
                    }
                }

            } else {
                result.push([item]);
            }

        })
        if(singleLevelArray.length){
            tempArray = []
            tempArray = singleLevelArray;
        }
        if(tempCount < len){
            createCombinations(tempCount++);
        }

        return result;

    }
    return createCombinations()
}

How to get all possible combinations of elements in an array including order and lengths

3 Answers3