Algorithm To Merge Two Arrays Into An Array Of All Possible Combinations

November 30, 2023 Post a Comment

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: mergeEveryW

Solution 1:

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

Solution 2:

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 -> aconstidentity = x =>
  x

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

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

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

// shift :: ((a -> b) -> cont a) -> cont bconstshift = f =>
  k => f (x => k (x) (identity))
  
// amb :: [a] -> cont [a]constamb = 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 ?

constpermute = (n, choices) =>
  {
    constloop = (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' ] ]

Solution 3:

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 = functionchain (f)
  {
    returnthis.reduce ((acc, x) =>
      acc.concat (f (x)), [])
  };

constpermute = (n, choices) =>
  {
    constloop = (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 ] ]constzippermute = (xs, ys) =>
  {
    constloop = (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

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

constpermute = (n, choices) =>
  {
    constloop = (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 ] ]constzippermute = (xs, ys) =>
  {
    constloop = (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' ] ]

Solution 4:

You can use lodash, here's their implementation:

(function(_) {

    _.mixin({combinations: function(values, n) {
        values = _.values(values);
        var combinations = [];
        (functionf(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 (typeofmodule !== 'undefined' && typeofexports !== 'undefined' && this === exports) {
        returnrequire('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

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

JavaScript College