Find all permutations of 2 arrays in JS

Question

I'm trying to find every permutations of 2 arrays like this:

// input
lowerWords = ['one', 'two', 'three' ] 
upperWords = [ 'ONE', 'TWO', 'THREE' ]

// output
keywords = {
  'one two three': true,
  'ONE two three': true,
  'ONE TWO three': true,
  'ONE TWO THREE': true,
  'ONE two THREE': true,
  'one TWO three': true,
  'one two THREE': true,
  'one TWO THREE': true,
}

It should function with more than 3 items, both arrays will always be same length. This is my code:

const keywords = {}
const lowerWords = ['one', 'two', 'three' ] 
const upperWords = [ 'ONE', 'TWO', 'THREE' ]
const wordCount = lowerWords.length

let currentWord = 0
let currentWords = [...upperWords]
while (currentWord < wordCount) {
  currentWords[currentWord] = lowerWords[currentWord]
  let keyword = currentWords.join(' ')
  keywords[keyword] = true
  currentWord++
}

currentWord = 0
currentWords = [...lowerWords]
while (currentWord < wordCount) {
  currentWords[currentWord] = upperWords[currentWord]
  let keyword = currentWords.join(' ')
  keywords[keyword] = true
  currentWord++
}

result is missing some

ONE TWO THREE: true
ONE TWO three: true
ONE two three: true
one TWO THREE: true
one two THREE: true
one two three: true

@Tigger no, those are combinations of 2, I need permutation of every item — Dave, May 22 '19 at 08:52
You are not looking for permutations (which are about order), but for the [cartesian product](https://stackoverflow.com/q/15298912/1048572) of `[one, ONE]`, `[two, TWO]` and `[three, THREE]`. You can get those by transposing your input. — Bergi, May 22 '19 at 18:32
@Bergi I'm not sure if your suggestion generalises to arbitrary input (see my comment under Nina Scholz's answer). — גלעד ברקן, May 22 '19 at 21:13

score 11 · Accepted Answer · answered May 22 '19 at 08:54

11

You could transpose the arrays for getting an array of pairs and then get all combinations of the pairs.

const
    transpose = array => array.reduce((r, a) => a.map((v, i) => [...(r[i] || []), v]), []),
    combinations = array => array.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

var lowerWords = ['one', 'two', 'three'],
    upperWords = ['ONE', 'TWO', 'THREE'],
    pairs = transpose([lowerWords, upperWords]),
    result = combinations(pairs);
    
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

answered May 22 '19 at 08:54

Nina Scholz

376,160
25
347
392

(This fails for the general version with `transpose([['ONE','TWO','THREE'],['one','two'], [1,2,3,4]])` compare with [mine](https://stackoverflow.com/a/56264734/2034787).) – גלעד ברקן May 22 '19 at 21:11
3

`transpose` transposes same length arrays. – Nina Scholz May 22 '19 at 21:14
@גלעדברקן It's unclear what output you'd want to get from that input anyway. – Bergi May 22 '19 at 21:16
@Bergi I implemented one such clarity. – גלעד ברקן May 22 '19 at 21:31
@גלעדברקן Well, with the transposed input format this really doesn't make sense. One should just call `cartesian([['one', 'ONE', 1], ['two','TWO', 2], ['three', 3], [4]])` if that kind of output is desired. – Bergi May 23 '19 at 06:53

Kobe · Answer 2 · 2019-05-22T10:36:56.180

Thought I'd give it a try. I used binary to get the possible combinations, as this problem needed a base 2 solution:

const low = ["one", "two", "three"];
const up = ["ONE", "TWO", "THREE"];

const words = [low, up]
const len = words[0].length


function getCombinations(noOfArrays, len) {
  var temp, newCombo, combos = [];
  for (var i = 0; i < (noOfArrays ** len); i++) {
    temp = new Array(len).fill(0)
    newCombo = i.toString(noOfArrays).split('');
    newCombo.forEach((el, i) => temp[temp.length - newCombo.length + i] = +el);
    combos.push(temp);
  }
  return combos;
}

function setCombinations(combos) {
  return combos.map(combo => combo.map((el, i) => words[el][i]))
}


var combos = getCombinations(words.length, len)
combos = setCombinations(combos)


console.log(combos)

Explanation of loop:

1. temp = new Array(len).fill(0)
2. newCombo = i.toString(2).split("");
3. newCombo.forEach((el, i) => temp[temp.length - newCombo.length + i] = +el);

Creates temp array [0,0,0]
Grabs loop number (i) and converts it to binary e.g:

1 -> 1
2 -> 10
3 -> 11
4 -> 100
etc...

Then split the binary into an array 100 -> [1,0,0].

Then for each element push it in that new array. This gave a problem with pushing the 1 and 2 element arrays (10 -> [1,0]) into the back of the array. I used temp.length - newCombo.length + i to fix that.

That function then returns:

[ 0, 0, 0 ]
[ 0, 0, 1 ]
[ 0, 1, 0 ]
[ 0, 1, 1 ]
[ 1, 0, 0 ]
[ 1, 0, 1 ]
[ 1, 1, 0 ]
[ 1, 1, 1 ]

Then, I can map over each combination, and grab each array depending on the value, and get the words ('one' or 'ONE') via loop index.

Note this code works with more than one array, as long as the arrays are all the same length.

Hi, I had *favorited* this question to come back later to provide an answer. My answer is very similar to yours (I independently came up, I swear :)). I have also added a generic version of it. Hope you don't mind. — adiga, May 22 '19 at 13:36
@adiga No problem, great minds think alike :p I like this approach because it's very scalable, since you can just change which base you are converting the index to for how many arrays the user provides. I didn't think about using padStart, either, so nicely done — Kobe, May 22 '19 at 13:53

adiga · Answer 3 · 2019-10-20T14:42:55.330

You need to get a total of 2 ^ 3 combinations. If you create a 2D matrix from the 2 arrays, the below table represents the row number from which of the item should be taken.

If you analyze indexes of the combinations, each of this a binary number from 0 to 2 ^ 3 with leading zeros.

So, you could

loop from 0 to 8
create binary number using toString(2)
Add leading zero using padStart
split each digit to get an array
Get each item from matrix[digit-from-binary][position-of-each-split]
join the array of items with a ' ' separator to get the key
Add the key to the output object

Working snippet:

function getAllCombinations(matrix) {
  const combinations = 2 ** 3,
        output = {};
  
  for(let i = 0; i < combinations; i++) {
      const key = i.toString(2)
                    .padStart(3, 0)
                    .split('')
                    .map((n, j) => matrix[n][j])
                    .join(" ")
                    
      output[key] = true;
  }
  
  return output
}

console.log(getAllCombinations([['one', 'two', 'three' ],[ 'ONE', 'TWO', 'THREE' ]]))

You can generalize this for m x n matrix. Instead of converting each to a binary number, you need to convert it to base-m and padStart to length n

function getAllCombinations(matrix) {
  const rows = matrix.length,
        columns = matrix[0].length,
        combinations = rows ** columns;

  return Array.from({ length: combinations },
    (_, i) => i.toString(rows)
                .padStart(columns, 0)
                .split('')
                .map((n, j) => matrix[n][j])
  )
}

console.log(JSON.stringify(
    getAllCombinations( [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ) // 3 x 3 matrix
));

console.log(JSON.stringify(
    getAllCombinations( [[1, 2], [3, 4], [5, 6], [7, 8]] ) // 4 x 2 matrix
));

.as-console-wrapper { max-height: 100% !important; top: 0; }

score 0 · Answer 4 · edited May 22 '19 at 11:06

Following Code should work for you its recursive approach:

const lowerWords = ['one', 'two', 'three']
const upperWords = ['ONE', 'TWO', 'THREE']

let result = {};

function getCombinations(index, caseType, arr) {
  if (index == 3) {
    arr[index] = (caseType == 'lower' ? lowerWords : upperWords)[index];
    result[arr.join(' ')] = true
    return
  }
  arr[index] = (caseType == 'lower' ? lowerWords : upperWords)[index];
  getCombinations(index + 1, 'lower', arr);
  getCombinations(index + 1, 'upper', arr);
}
getCombinations(0, 'lower', [])
getCombinations(0, 'upper', [])

console.log('resultresult', result)

גלעד ברקן · Answer 5 · 2019-07-28T13:33:31.107

We can enumerate these directly. Here's one algorithm:

If we've reached the end of
the list, return the combination
the current recursion branch is
building.

Otherwise, create a new branch
that picks the next item from B,
while the current branch picks
the next item from A.

JavaScript code:

function f(A, B, i=0, comb=[]){
  return i == A.length
         ? [comb]
         : f(A, B, i + 1, comb.concat(A[i])).concat(
           f(A, B, i + 1, comb.slice().concat(B[i])))
}

console.log(JSON.stringify(f(['one','two','three'], ['ONE','TWO','THREE'])))

גלעד ברקן · Answer 6 · 2019-05-24T10:30:47.043

Here's a generalised version based on my other answer that handles a variable number of input arrays with varying lengths:

const g = (arrs, i=0, comb=[]) =>
  !arrs.some(arr => i < arr.length)
  ? [comb]
  : arrs.reduce((acc, arr) => 
      i >= arr.length ? acc :
      acc.concat(g(arrs, i + 1, comb.slice().concat(arr[i])))
    , [])
    

// Example output
let input = [['ONE','TWO','THREE'], ['one','two'], [1,2,3,4]]

let str = ''
for (let line of g(input))
  str += JSON.stringify(line) + '\n'
console.log(str)

Find all permutations of 2 arrays in JS

6 Answers6

Linked

Related