算法将两个数组合并成所有可能组合的数组 [英] algorithm to merge two arrays into an array of all possible combinations

问题描述

在JavaScript中给出的例子：假设我们有两个数组[0,0,0]和[1,1,1]。产生这两种阵列可以结合的所有可能方式的算法是什么？例子：

  mergeEveryWayPossible（[0,0,0]，[1,1,1]）$ ​​b $ b // [[0,0,0]，[1,0,0]，[0,1,0]，[0,0,1]，[1,1,0]，[0,1,1]，[ 1,0,1]，[1,1,1]] 
  

将数组合并到一个数组中所有可能的组合。这与寻找笛卡尔产品不同。

我也不确定这种组合是怎么称呼的。如果算法或技术有名字，请分享。

解决方案

列表monad

写了很长一段时间关于划定whatchamacallits 是坚果 - 在花了3个小时我试图找出它，我会忘记一切都在30秒内完成！

更为严重的是，与此答案相比， shift / reset 是如此令人难以置信的不切实际，这是一个笑话。但是，如果我不先分享这个答案，我们就不会有将内心彻底放弃的喜悦！因此，请不要触及转移 / 重置，除非他们对于手头的任务至关重要 - 请请原谅我，如果你觉得自己被骗学习了一些非常酷的东西的话！

让我们不要忽视一个更直接的解决方案，List monad - code> Array.prototype.chain 在这里 - 同样，注意这个解决方案和延续解决方案之间的结构相似之处。

  // monads不必吓倒//这里有两行一行†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,0,1]，// [1,1,0]，// [1,1,1]] const zippermute =（xs，ys）=> {const loop =（acc，[x，... xs]，[y，... ys]）=> x === undefined || y ===未定义？ [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 a ）和绑定（ Monad a - >（a - > Monad b） - > Monad b ）函数 - chain 是我们的 bind 在这里，JavaScript的数组字面语法（ [someValue] ）提供了我们的单元 - 这就是它的全部内容

---

哦，您无法触及原生原型！
$ b

好的，有时候不要触摸原生原型是很好的理由。不要担心，只需为Arrays创建一个数据构造函数;我们将它称为 List - 现在我们有一个地方来定义我们想要的行为

如果你喜欢这个解决方案，您可能会发现我写的另一个答案很有用;该程序使用列表monad使用查询路径从数据源中提取一个或多个值

  const List =（xs = []）=> （{value：xs，chain：f => List（xs.reduce（（acc，x）=> acc.concat（f（x）.value），[]））}）const permute =（n，选择）=> {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 ===未定义？ List（[acc]）：List（[x，y]）。chain（choice => loop（acc.concat（[choice]），xs，ys））return loop（[]，xs，ys）.value } console.log（['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']]  

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.

解决方案

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

这篇关于算法将两个数组合并成所有可能组合的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！