algorithm to merge two arrays into an array of all possible combinations

Question

Example given in JavaScript:

Suppose we have two arrays [0,0,0] and [1,1,1]. What's the algorithm to produce all possible ways these two arrays can be combine. Example:

mergeEveryWayPossible([0,0,0],[1,1,1])
// [ [0,0,0],[1,0,0], [0,1,0], [0,0,1], [1,1,0], [0,1,1], [1,0,1], [1,1,1] ]

merge the arrays into an array of all possible combinations. This is different than finding the cartesian product.

I'm also not sure what this kind of combination is called. If the algorithm or technique has a name, please share.

Answer 1

List monad

Whoever wrote that long thing about delimited whatchamacallits is nuts – after the 3 hours I spend trying to figure it out, I'll forget everything about it in 30 seconds !

On a more serious note, when compared to this answer, the shift/reset is so unbelievably impractical, it's a joke. But, if I didn't share that answer first, we wouldn't have had the joy of turning our brains inside out ! So please, don't reach for shift/reset unless they're critical to the task at hand – and please forgive me if you feel cheated into learning something totally cool !

Let's not overlook a more straightforward solution, the List monad – lovingly implemented with Array.prototype.chain here – also, notice the structural similarities between this solution and the continuation solution.

// monads do not have to be intimidating
// here's one in 2 lines†
Array.prototype.chain = function chain (f)
  {
    return this.reduce ((acc, x) =>
      acc.concat (f (x)), [])
  };

const permute = (n, choices) =>
  {
    const loop = (acc, n) =>
      n === 0
        ? [acc]
        : choices.chain (choice =>
            loop (acc.concat ([choice]), n - 1))
    return loop ([], n)
  }

console.log (permute (3, [0,1]))
// [ [ 0, 0, 0 ],
//   [ 0, 0, 1 ],
//   [ 0, 1, 0 ],
//   [ 0, 1, 1 ],
//   [ 1, 0, 0 ],
//   [ 1, 0, 1 ],
//   [ 1, 1, 0 ],
//   [ 1, 1, 1 ] ]

const zippermute = (xs, ys) =>
  {
    const loop = (acc, [x,...xs], [y,...ys]) =>
      x === undefined || y === undefined
        ? [acc]
        : [x,y].chain (choice =>
            loop (acc.concat ([choice]), xs, ys))
    return loop ([], xs, ys)
  }

console.log (zippermute (['a', 'b', 'c'], ['x', 'y', 'z']))
// [ [ 'a', 'b', 'c' ],
//   [ 'a', 'b', 'z' ],
//   [ 'a', 'y', 'c' ],
//   [ 'a', 'y', 'z' ],
//   [ 'x', 'b', 'c' ],
//   [ 'x', 'b', 'z' ],
//   [ 'x', 'y', 'c' ],
//   [ 'x', 'y', 'z' ] ]

† a monad interface is made up of some unit (a -> Monad a) and bind (Monad a -> (a -> Monad b) -> Monad b) functions – chain is our bind here, and JavaScript's array literal syntax ([someValue]) provides our unit – and that's all there is to it

---

Oh, you can't touch native prototypes !!

OK, sometimes there's good reason not to touch native prototypes. Don't worry tho, just create a data constructor for Arrays; we'll call it List – now we have a place to define our intended behaviours

If you like this solution, you might find another answer I wrote useful; the program employs the list monad to fetch 1 or more values from a data source using a query path

const List = (xs = []) =>
  ({
    value:
      xs,
    chain: f =>
      List (xs.reduce ((acc, x) =>
        acc.concat (f (x) .value), []))
  })

const permute = (n, choices) =>
  {
    const loop = (acc, n) =>
      n === 0
        ? List ([acc])
        : List (choices) .chain (choice =>
            loop (acc.concat ([choice]), n - 1))
    return loop ([], n) .value
  }

console.log (permute (3, [0,1]))
// [ [ 0, 0, 0 ],
//   [ 0, 0, 1 ],
//   [ 0, 1, 0 ],
//   [ 0, 1, 1 ],
//   [ 1, 0, 0 ],
//   [ 1, 0, 1 ],
//   [ 1, 1, 0 ],
//   [ 1, 1, 1 ] ]

const zippermute = (xs, ys) =>
  {
    const loop = (acc, [x,...xs], [y,...ys]) =>
      x === undefined || y === undefined
        ? List ([acc])
        : List ([x,y]).chain (choice =>
            loop (acc.concat ([choice]), xs, ys))
    return loop ([], xs, ys) .value
  }

console.log (zippermute (['a', 'b', 'c'], ['x', 'y', 'z']))
// [ [ 'a', 'b', 'c' ],
//   [ 'a', 'b', 'z' ],
//   [ 'a', 'y', 'c' ],
//   [ 'a', 'y', 'z' ],
//   [ 'x', 'b', 'c' ],
//   [ 'x', 'b', 'z' ],
//   [ 'x', 'y', 'c' ],
//   [ 'x', 'y', 'z' ] ]

Answer 2

You could transform the value to an array to this format

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

and then build a new result set by iterating the outer and inner arrays.

var data = [[0, 0, 0], [1, 1, 1]],
    values = data.reduce((r, a, i) => (a.forEach((b, j) => (r[j] = r[j] || [])[i] = b), r), []),
    result = values.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
    
console.log(result);

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

Answer 3

continuations

Here's a solution involving delimited continuations – delimited continuations are sometimes called composable continuations because they have a return value, and thus can be composed with any other ordinary functions – additionally, they can be called multiple times which can produce extraordinary effects

// identity :: a -> a
const identity = x =>
  x

// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = f => ([x,...xs]) =>
  x === undefined
    ? []
    : f (x) .concat (concatMap (f) (xs))

// cont :: a -> cont a
const cont = x =>
  k => k (x)

// reset :: cont a -> (a -> b) -> b
const reset = m =>
  k => m (k)

// shift :: ((a -> b) -> cont a) -> cont b
const shift = f =>
  k => f (x => k (x) (identity))
  
// amb :: [a] -> cont [a]
const amb = xs =>
  shift (k => cont (concatMap (k) (xs)))

// demo
reset (amb (['J', 'Q', 'K', 'A']) (x =>
         amb (['?', '?', '?', '?']) (y =>
           cont ([[x, y]]))))
      (console.log)
      
// [ ['J','?'], ['J','?'], ['J','?'], ['J','?'], ['Q','?'], ['Q','?'], ['Q','?'], ['Q','?'], ['K','?'], ['K','?'], ['K','?'], ['K','?'], ['A','?'], ['A','?'], ['A','?'], ['A','?'] ]

Of course this works for any variety of inputs and any nesting limit (that doesn't blow the stack ^_^)

const choices =
  [0,1]

reset (amb (choices) (x =>
        amb (choices) (y =>
          amb (choices) (z =>
            cont ([[x, y, z]])))))
      (console.log)

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

But you must be wondering how we can abstract the nesting of amb itself – for example, in the code above, we have 3 levels of nesting to generate permutations of length 3 – what if we wanted to permute our choices 4, 5, or N times ?

const permute = (n, choices) =>
  {
    const loop = (acc, n) =>
      n === 0
        ? cont ([acc])
        : amb (choices) (x =>
            loop (acc.concat ([x]), n - 1))
    return loop ([], n)
  }

permute (4, [true,false]) (console.log)
// [ [ true , true , true , true  ],
//   [ true , true , true , false ],
//   [ true , true , false, true  ],
//   [ true , true , false, false ],
//   [ true , false, true , true  ],
//   [ true , false, true , false ],
//   [ true , false, false, true  ],
//   [ true , false, false, false ],
//   [ false, true , true , true  ],
//   [ false, true , true , false ],
//   [ false, true , false, true  ],
//   [ false, true , false, false ],
//   [ false, false, true , true  ],
//   [ false, false, true , false ],
//   [ false, false, false, true  ],
//   [ false, false, false, false ] ]

---

sounds german, or something

If I'm understanding your comment correctly, you want something that zips the input and permutes each pair – shall we call it, zippermute ?

const zippermute = (xs, ys) =>
  {
    const loop = (acc, [x,...xs], [y,...ys]) =>
      x === undefined || y === undefined
        ? cont ([acc])
        : amb ([x,y]) (choice =>
            loop (acc.concat ([choice]), xs, ys))
    return loop ([], xs, ys)
  }

zippermute (['a', 'b', 'c'], ['x', 'y', 'z']) (console.log)
// [ [ 'a', 'b', 'c' ],
//   [ 'a', 'b', 'z' ],
//   [ 'a', 'y', 'c' ],
//   [ 'a', 'y', 'z' ],
//   [ 'x', 'b', 'c' ],
//   [ 'x', 'b', 'z' ],
//   [ 'x', 'y', 'c' ],
//   [ 'x', 'y', 'z' ] ]

Answer 4

You can use lodash, here's their implementation:

(function(_) {

    _.mixin({combinations: function(values, n) {
        values = _.values(values);
        var combinations = [];
        (function f(combination, index) {
            if (combination.length < n) {
                _.find(values, function(value, index) {
                    f(_.concat(combination, [value]), index + 1);
                }, index);
            } else {
                combinations.push(combination);
            }
        })([], 0);
        return combinations;
    }});

})((function() {
    if (typeof module !== 'undefined' && typeof exports !== 'undefined' && this === exports) {
        return require('lodash');
    } else {
        return _;
    }
}).call(this));

console.log(_.combinations('111000', 3))
console.log(_.combinations('111000', 3).length + " combinations available");

This would log out the following:

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

"20 combinations available"

There library is at https://github.com/SeregPie/lodash.combinations

Answer 5

Note that for arrays length N there are 2^N combinations. Every integer number in range 0..2^N-1 corresponds to some combination: if k-th bit of number is zero then get k-th element of result from the first array, otherwise - from the second.

P.S. Note that your example is equivalent to binary representation of numbers.

Answer 6

This was a fun problem that I encountered and upon reading the answers to listed here, I figured a more readable less clever answer might be good for newcomers.

This treats each array that needs to be comibined together like an individual digit that increments up to that digit's highest value (the array length - 1).

With all of the digits representing the arrays, it is a matter of incrementing the set, carrying any ones, and eventually looping back around to all zeros again in the counter to indicate that we have completed the set.

This also makes it so we don't have to do any recursion and it can be just done with a while loop.

function allPermutationsOfArrays(arrayOfArrays) {
  const out = [];
  // this counter acts like an incrementing number
  const incrementalSet = arrayOfArrays.map(() => 0);
  // max values for each "digit" of the counter
  const maxValues = arrayOfArrays.map((a) => a.length - 1);
  while (1) {
    const outRow = [];
    // for the current counter incrementer, get the array values and 
    // put them together for output
    for (let i = 0; i < incrementalSet.length; i++) {
      outRow[i] = arrayOfArrays[i][incrementalSet[i]];
    }
    out.push(outRow);
    //add one to incremental set - we are going right to left so it works like
    // normal numbers, but really that is arbitrary and we could go left to right
    let allZeros = true;
    for (let i = incrementalSet.length - 1; i >= 0; i--) {
      if (incrementalSet[i] + 1 > maxValues[i]) {
        incrementalSet[i] = 0;
        continue; //carry the one to the next slot
      } else {
        incrementalSet[i] += 1;
        allZeros = false;
        break; // nothing to carry over
      }
    }
    if (allZeros) {
      // we have done all combinations and are back to [0, 0,...];
      break; // break the while(1) loop
    }
  }
  return out;
}
console.log(
  allPermutationsOfArrays([
    [0, 1, 2],
    ["a", "b"],
  ])
);
// [
//   [ 0, 'a' ],
//   [ 0, 'b' ],
//   [ 1, 'a' ],
//   [ 1, 'b' ],
//   [ 2, 'a' ],
//   [ 2, 'b' ]
// ]