JavaScript - Generating Combinations from N Arrays With M Elements

JavaScript - Generating combinations from n arrays with m elements

Here is a quite simple and short one using a recursive helper function:

function cartesian(...args) {
    var r = [], max = args.length-1;
    function helper(arr, i) {
        for (var j=0, l=args[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(args[i][j]);
            if (i==max)
                r.push(a);
            else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
}

Usage:

cartesian([0,1], [0,1,2,3], [0,1,2]);

To make the function take an array of arrays, just change the signature to function cartesian(args) instead of using rest parameter syntax.

Generating combinations from multiple Arrays of object

I try to add my thought into comment but the space is not enough.

Not sure about what constraints you actually have. Probably you can list out all possibility from all arrays and then make all combinations later to reduce the time complexity;

For example, convert all values from input arrays to a map like the following

{
  //I highly suggest use a set here instead of a list so you don't need to 
  //worry about duplicate number while adding new values
  1: [1, 12 ,13],
  2: [2, 21],
  3: [3],
  4: [4],
  5: [5],
}

then you can combine all values from a n arrays, which it's already answer from the past:
JavaScript - Generating combinations from n arrays with m elements.

This is the best solution I can imagine theoretically since you only have the extra O(sum of all arrays size) + the combination cost, in which I don't believe there are much space you can reduce.

Javascript - Generating all combinations of elements in a single array (in pairs)

A simple way would be to do a double for loop over the array where you skip the first i elements in the second loop.

let array = ["apple", "banana", "lemon", "mango"];

let results = [];

// Since you only want pairs, there's no reason

// to iterate over the last element directly

for (let i = 0; i < array.length - 1; i++) {

  // This is where you'll capture that last value

  for (let j = i + 1; j < array.length; j++) {

    results.push(`${array[i]} ${array[j]}`);

  }

}

console.log(results);

Creating a combination from arrays and turn it into a multi-dimensional permutations in javascript?

You are looking to get the subsets of length N from your selection of arrays, then create the cartesian product of each subset.

// returns power set of arr filtered by length
function powerset(arr, len, pref=[]) {
    if (len == 0) return [pref];
    if (len > arr.length) return [];
    if (len == arr.length) return [pref.concat(arr)]; // premature optimisation
    const next = arr.slice(1);
    return powerset(next, len-1, [...pref, arr[0]]).concat(powerset(next, len, pref));
}
// returns cartesian product of the arrays in the argument
function cartesian(arg) {
    var r = [], max = arg.length-1;
    function helper(arr, i) {
        for (var j=0, l=arg[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(arg[i][j]);
            if (i==max)
                r.push(a);
            else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
}

var arrays = [
  ['a', 'b'],
  ['c'],
  ['d', 'e', 'f'],
  ['x', 'y', 'z']
];
console.log(powerset(arrays, 2).flatMap(cartesian));
console.log(powerset(arrays, 3).flatMap(cartesian));
console.log(powerset(arrays, 4).flatMap(cartesian));

How can I create every combination possible for the contents of two arrays?

A loop of this form

combos = [] //or combos = new Array(2);

for(var i = 0; i < array1.length; i++)
{
     for(var j = 0; j < array2.length; j++)
     {
        //you would access the element of the array as array1[i] and array2[j]
        //create and array with as many elements as the number of arrays you are to combine
        //add them in
        //you could have as many dimensions as you need
        combos.push(array1[i] + array2[j])
     }
}

Find all sets of length n combinations of m arrays

You basically want to find every permutation of every array and combine them. This can be done recursively:

function permutate(arr) {
    // every array of length one is already permutated
    if (arr.length == 1) return [ arr ];
    let permutations = [];
    for (let i = 0; i < arr.length; i++) {
        // Remove the current element and permutate the rest
        let sub = permutate(arr.splice(i, 1));
        // Insert current element into every permutation
        sub = sub.map(x => [arr[i], ...x]);
        // Add permutations to list
        permutations.push(...sub);
    }
    return permutations;
}

Next the combine function:

function combine(arrays, current = [], i = 0) {
    if (i == arrays.length)
        return [ current ];

    let values = [];

    for (let j = 0; j < arrays[i].length; j++) {
        let temp = current.slice();
        temp.push(arrays[i][j]);
        values.push(...combine(arrays, temp, i + 1));
    }

    return values;
}

// If you get a call stack size exceeded (stackoverflow) error, you can replace
// this using nested for loops. For instance for 5 arrays with 5 elements each:
let sets = [];
for (let i = 0; i < permutations[0].length; i++) {
  for (let j = 0; j < permutations[1].length; j++) {
    for (let k = 0; k < permutations[2].length; k++) {
      for (let l = 0; l < permutations[3].length; l++) {
        for (let m = 0; m < permutations[4].length; m++) {
            let set = [];
            for (let n = 0; n < 5; n++) {
                set.push([ permutations[0][i][n], permutations[1][j][n], permutations[2][k][n], permutations[3][l][n], permutations[4][m][n] ]);
            }
            sets.push(set);
        }
      }
    }
  }
}

By first permutating every array (which results in 24 different permutations for each one), then combining these (which is 24^4=331776 combinations), you'll get everything you need to construct the arrays. Just loop over every combination and put the elements at the same indices into the same set:

let permutations = [ array1, array2, array3, array4 ].map(arr => permutate(arr));

let sets = combine(permutations);
let out = [];
for (let i = 0; i < sets.length; i++) {
    let set = [];
    for (let j = 0; j < 4; j++) {
        set.push([ sets[i][0][j], sets[i][1][j], sets[i][2][j], sets[i][3][j] ]);
    }
    out.push(set);
}

Working example:

array1 = ['a', 'b', 'c', 'd'];

array2 = ['e', 'f', 'g', 'h'];

array3 = ['i', 'j', 'k', 'l'];

array4 = ['m', 'n', 'o', 'p'];

function permutate(arr) {

  if (arr.length == 1) return [ arr ];

  let permutations = [];

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

    let temp = arr.slice();

    temp.splice(i, 1);

    let sub = permutate(temp);

    sub = sub.map(x => [arr[i], ...x]);

    permutations.push(...sub);

  }

  return permutations;

}

function combine(arrays, current = [], i = 0) {

 if (i == arrays.length)

  return [ current ];

 

 let values = [];

 

 for (let j = 0; j < arrays[i].length; j++) {

  let temp = current.slice();

  temp.push(arrays[i][j]);

  values.push(...combine(arrays, temp, i + 1));

 }

 

 return values;

}

let permutations = [ array1, array2, array3, array4 ].map(arr => permutate(arr));

console.log(permutations);

let sets = combine(permutations);

let out = [];

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

 let set = [];

 for (let j = 0; j < 4; j++) {

  set.push([ sets[i][0][j], sets[i][1][j], sets[i][2][j], sets[i][3][j] ]);

 }

 out.push(set);

}

console.log(out);

---

Related Topics