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!
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 )
R.lift which infers this for you. BTW, I prefer fixed arity functions (i.e. lift3) 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.
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; }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).
