CODEWITHSUNDEEP
javascriptalgorithmpermutation
Marco Afonso
Marco Afonso

Reputation: 316

Generate permutations of multi array

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!

Upvotes: 3

Views: 462

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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).

Upvotes: 1

Mat&#237;as Fidemraizer
Mat&#237;as Fidemraizer

Reputation: 64933

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 )

Upvotes: 3

Nina Scholz
Nina Scholz

Reputation: 386620

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; }

Upvotes: 1

Jonas Wilms
Jonas Wilms

Reputation: 138267

 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.

Upvotes: 2

Related Questions