Generate permutations of multi array

Question

I would like to generate all permutations of elements in a multi array in javascript (or the algorithm):

Input:

[
  ['a', 'b', 'c', 'd'],
  ['e', 'f', 'g'],
  ['h', 'i']
]

Output:

[
  ['a', 'e', 'h'],
  ['a', 'e', 'i'],
  ['a', 'f', 'h'],
  ...
  ['d', 'g', 'i']
]

Note: I don't want the permutations of ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'] because i don't want results like: ['a', 'b', 'c'].

Note2: I'm only interested in solutions that support input of N-dimension array.

Thanks!

Duplicate of https://stackoverflow.com/questions/9960908/permutations-in-javascript — Attersson, May 20 '18 at 11:26
Possible duplicate of [Permutations in JavaScript?](https://stackoverflow.com/questions/9960908/permutations-in-javascript) — Attersson, May 20 '18 at 11:26
Loop through all array in the array and get a list of unique item. After, it should be easy to get permutations of your size as we already have so many posts on how to get permutations. — Anh Pham, May 20 '18 at 11:31
@Attersson In https://stackoverflow.com/questions/9960908/permutations-in-javascript the output is the permutations of each array element, here the output is the permutations of the inner elements of the elements of the input. — Marco Afonso, May 20 '18 at 11:32

Matías Fidemraizer · Answer 1 · 2018-05-20T13:50:39.387

If you like functional programming, you can use lift on Array type. In my case, I've used RamdaJS for the sake of simplicity:

const input = [
  ['a', 'b', 'c', 'd'],
  ['e', 'f', 'g'],
  ['h', 'i']
]

const output = R.lift ( ( x, y, z ) => [ x, y, z ] ) ( ...input )

console.log( output )

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.25.0/ramda.min.js"></script>

Here's a vanilla JavaScript lift3 implementation:

const input = [
  ['a', 'b', 'c', 'd'],
  ['e', 'f', 'g'],
  ['h', 'i']
]

const flatten = array => [].concat.apply ( [], array )

// Array#flatMap please! ;-)
const ap = funs => array => flatten ( funs.map ( f => array.map ( f ) ) )

const lift3 = f => array1 => array2 => array3 => 
                ap ( ap ( array1.map ( f ) ) ( array2 ) ) ( array3 )

const output = lift3 ( x => y => z => [ x, y, z ] ) ( input[0] ) ( input[1] ) ( input[2] )

console.log( output )

do you need to specify the length and take n parameter for it (and the corresponding array)? — Nina Scholz, May 20 '18 at 11:59
@NinaScholz No, I've switched to `R.lift` which infers this for you. BTW, I prefer fixed arity functions (i.e. `lift3`) — Matías Fidemraizer, May 20 '18 at 13:00

Jonas Wilms · Accepted Answer · 2018-05-20T11:43:16.013

2

 function mutate(array) {
   if(array.length === 1)
      return array[0].map(el => [el]);
   const mutations = mutate(array.slice(1));
   const result = [];
   for(const el of array[0])
     for(const rest of mutations)
       result.push([el, ...rest]);
   return result;
}

This is a recursive approach.

edited May 20 '18 at 11:43

answered May 20 '18 at 11:30

Jonas Wilms

132,000
20
149
151

score 1 · Answer 3 · answered May 20 '18 at 11:47

You could use an iterative and recursive approach.

var d = [['a', 'b', 'c', 'd'], ['e', 'f', 'g'], ['h', 'i']],
    processor = array => {
         var result = [],
             iter = p => p.length < array.length
                ? array[p.length].forEach(v => iter(p.concat(v)))
                : result.push(p);

        iter([]);
        return result;
    };

console.log(processor(d).map(a => a.join(' ')));

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

A shorter approach

var d = [['a', 'b', 'c', 'd'], ['e', 'f', 'g'], ['h', 'i']],
    result = d.reduce(
        (a, b) => a.reduce(
            (r, v) => r.concat(b.map(w => [].concat(v, w))),
            []
        )
    );

console.log(result.map(a => a.join(' ')));

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

גלעד ברקן · Answer 4 · 2018-05-22T09:56:55.880

What you seem to be interested in is a cartesian product of the sets. The length of the output will be the product of the sets' lengths and we can derive the list index of each element in an arbitrary output list by the following method:

// i is the zero-based ouput-list index
// p is the product of input set lengths
function unrank(i, input, p){
  let output_list = new Array(input.length);

  for (let k=0; k<input.length; k++){
    p = Math.floor(p / input[k].length);
    let m = Math.floor(i / p);
    i = i - m * p;
    output_list[k] = input[k][m];
  }
  
  return output_list;
}

var input = [
  ['a', 'b', 'c', 'd'],
  ['e', 'f', 'g'],
  ['h', 'i']
];

// Output
var prod = input.map(x => x.length).reduce((a, b) => a * b);

console.log(unrank(23, input, prod));
console.log(unrank(11, input, prod));

To list them all, loop over the indexes from 0 to (product of input set lengths - 1).

Generate permutations of multi array

4 Answers4