An algorithm for combining two arrays into an array of all possible combinations

Question

JavaScript example:

Suppose we have two arrays [0,0,0] and [1,1,1]. What an algorithm to create all possible ways to combine these two arrays. 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] ]

combine arrays into an array of all possible combinations. This is different from finding a Cartesian product.

I'm also not sure what is called such a combination. If the algorithm or method has a name, share it.

Answer 1

Monad List

The one who wrote this long thing about the divisible whatchamacallits is nuts - after I spent three hours figuring it out, I will forget everything about it in 30 seconds

, , shift/reset , . , , ! , , shift/reset, - , , , - !

, List, Array.prototype.chain , .

// monads do not have to be intimidating
// here 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' ] ]

Hide result

† monad (a -> Monad a) bind (Monad a -> (a -> Monad b) -> Monad b) - chain - , JavaScript ([someValue]) - , ,

---

, !

, . , ; List -

, , , ; 1

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' ] ]

Hide result

Answer 2

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

, .

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

Hide result

Answer 3

- , - , ,

// 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','♧'] ]

Hide result

, ( ^ _ ^)

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] ]

, amb - , , 3 3 - , 4, 5 N ?

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 ] ]

---

-

, -, - , 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

lodash, :

(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");

:

[[ "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"

The library is https://github.com/SeregPie/lodash.combinations

Answer 5

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

PS Please note that your example is equivalent to the binary representation of numbers.