1

Objective: Find all sets of length n combinations of m arrays, such that index i of each item in a set is not the same as i in any other element of that set

I have the following arrays:

array1 = ['a', 'b', 'c', 'd'];
array2 = ['e', 'f', 'g', 'h'];
array3 = ['i', 'j', 'k', 'l'];
array4 = ['m', 'n', 'o', 'p'];

I would like to find every possible combination of these taking one element from each array, but then place those combinations into sets such that index i of any element in a given set is different to index i of another element in that same set. For instance, one set could be:

[ 
  { 1: "a", 2: "e", 3: "i", 4: "m" }, 
  { 1: "b", 2: "f", 3: "j", 4: "n" }, 
  { 1: "c", 2: "g", 3: "k", 4: "o" }, 
  { 1: "d", 2: "h", 3: "l", 4: "p" }
]

as every property '1' is different and taken from array1, every property '2' is different and taken from array2, etc.

Now I need to find every possible one of these.

I've tried looking at this post and implement it by creating combinations of combinations before filtering out everything invalid and cycling through to establish sets, but of course this missed many and took almost an hour to run on this example. Therefore, I need a more systematic approach to speed up the process and make it neater.

mplungjan
  • 169,008
  • 28
  • 173
  • 236
Geza Kerecsenyi
  • 1,127
  • 10
  • 27

1 Answers1

0

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);
Bálint
  • 4,009
  • 2
  • 16
  • 27