# JavaScript - Generating combinations from n arrays with m elements

I'm having trouble coming up with code to generate combinations from n number of arrays with m number of elements in them, in JavaScript. I've seen similar questions about this for other languages, but the answers incorporate syntactic or library magic that I'm unsure how to translate.

Consider this data:

``````[[0,1], [0,1,2,3], [0,1,2]]
``````

3 arrays, with a different number of elements in them. What I want to do is get all combinations by combining an item from each array.

For example:

``````0,0,0 // item 0 from array 0, item 0 from array 1, item 0 from array 2
0,0,1
0,0,2
0,1,0
0,1,1
0,1,2
0,2,0
0,2,1
0,2,2
``````

And so on.

If the number of arrays were fixed, it would be easy to make a hard coded implementation. But the number of arrays may vary:

``````[[0,1], [0,1]]
[[0,1,3,4], [0,1], , [0,1]]
``````

Any help would be much appreciated.

36

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.

Tuesday, June 1, 2021

21

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);``````

Rewritten with ES5:

``````var array = ["apple", "banana", "lemon", "mango"];
var results = [];

// Since you only want pairs, there's no reason
// to iterate over the last element directly
for (var i = 0; i < array.length - 1; i++) {
// This is where you'll capture that last value
for (var j = i + 1; j < array.length; j++) {
results.push(array[i] + ' ' + array[j]);
}
}

console.log(results);``````
Thursday, June 3, 2021

15

``````Mary <1> had <2> a <3> little <4> lamb
``````

Each of these `<number>`s can be either true or false. If it is true, then you cut the sentence in that location.

So, if you have n+1 words, your problem gets reduced to going through binary representation of numbers with n bit, that is from 0 to 2^n-1

Examples:

``````0110 -> {'Mary had', 'a', 'little lamb'}
1111 -> {'Mary', 'had', 'a', 'little', 'lamb'}
0001 -> {'Mary had a little', 'lamb'}
1011 -> {'Mary', 'had a', 'little', 'lamb'}
``````
Saturday, August 28, 2021

67

The problem, besides using index `n` where you should be using `n - 1` is that you assume the array must be copied between calls (i.e. immutable behaviour).

The algorithm assumes that the array is always the same in each recursive step, so thanks to how JavaScript handles scope you can greatly simplify the code:

``````function permutationArr(num)
{
var arr = (num + '').split(''),
permutations = [];

function swap(a, b)
{
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

function generate(n) {
if (n == 1) {
permutations.push(arr.join());
} else {
for (var i = 0; i != n; ++i) {
generate(n - 1);
swap(n % 2 ? 0 : i, n - 1);
}
}
}

generate(arr.length);
return permutations;
}

console.log(permutationArr(1234)); ``````

### Output

``````["1,2,3,4", "2,1,3,4", "3,1,2,4", "1,3,2,4", "2,3,1,4", "3,2,1,4", "4,2,3,1",
"2,4,3,1", "3,4,2,1", "4,3,2,1", "2,3,4,1", "3,2,4,1", "4,1,3,2", "1,4,3,2",
"3,4,1,2", "4,3,1,2", "1,3,4,2", "3,1,4,2", "4,1,2,3", "1,4,2,3", "2,4,1,3",
"4,2,1,3", "1,2,4,3", "2,1,4,3"]
``````
Monday, September 27, 2021

90

Use `combn()` with `lapply()` should do the trick.

``````x <- c('red', 'blue', 'green', 'red', 'green', 'red')

lapply(1:3, function(y) combn(x, y))

# []
# [,1]  [,2]   [,3]    [,4]  [,5]    [,6]
# [1,] "red" "blue" "green" "red" "green" "red"

# []
# [,1]   [,2]    [,3]  [,4]    [,5]  [,6]    ...
# [1,] "red"  "red"   "red" "red"   "red" "blue"  ...
# [2,] "blue" "green" "red" "green" "red" "green" ...

# []
# [,1]    [,2]   [,3]    [,4]   [,5]    [,6]    ...
# [1,] "red"   "red"  "red"   "red"  "red"   "red"   ...
# [2,] "blue"  "blue" "blue"  "blue" "green" "green" ...
# [3,] "green" "red"  "green" "red"  "red"   "green" ...
``````

All unique combinations

``````lapply(cc, function(y)
y[,!duplicated(apply(y, 2, paste, collapse="."))]
)

[]
 "red"   "blue"  "green"

[]
[,1]   [,2]    [,3]  [,4]    [,5]   [,6]    [,7]
[1,] "red"  "red"   "red" "blue"  "blue" "green" "green"
[2,] "blue" "green" "red" "green" "red"  "red"   "green"

[]
[,1]    [,2]   [,3]    [,4]    [,5]    [,6]  [,7]    ...
[1,] "red"   "red"  "red"   "red"   "red"   "red" "blue"  ...
[2,] "blue"  "blue" "green" "green" "red"   "red" "green" ...
[3,] "green" "red"  "red"   "green" "green" "red" "red"   ...
``````

Although strictly speaking those aren't all unique combinations, as some of them are permutations of each other.

Properly unique combinations

``````lapply(cc, function(y)
y[,!duplicated(apply(y, 2, function(z) paste(sort(z), collapse=".")))]
)

# []
#  "red"   "blue"  "green"

# []
# [,1]   [,2]    [,3]  [,4]    [,5]
# [1,] "red"  "red"   "red" "blue"  "green"
# [2,] "blue" "green" "red" "green" "green"

# []
# [,1]    [,2]   [,3]    [,4]    [,5]  [,6]
# [1,] "red"   "red"  "red"   "red"   "red" "blue"
# [2,] "blue"  "blue" "green" "green" "red" "green"
# [3,] "green" "red"  "red"   "green" "red" "green"
``````
Saturday, November 6, 2021