multi-dimentonal objects 数组中的笛卡尔积（所有组合），长度灵活

Question

Whosebug 上有几个问题和答案，其中显示了如何为各种简单数组查找笛卡尔积。还有一篇关于 RosettaCode 的精彩文章。但是我找不到解决我的问题的方法。

我有一个包含项目的 object 数组，我们称它为 items:

let items = [{
   id: 1
   quantity: 2
   field: "other_field"
},
{
   id: 2
   quantity: 3
   field: "other_field"
}]

这个数组中的每个项目都有一个 pricing/crafting 方法，我们可以通过请求接收它。

let pricing = getPricing(id) //item id

/*
Which will return to us:
*/

pricing = [
    {pricing_id: 1, reagent_items: [/*array of objects, fields exactly items*/]},
    {pricing_id: 2, reagent_items: [/*array of objects, fields exactly items*/]}
]

笛卡尔积问题：

您可能已经了解，根据答案的标题，我想从定价方法中接收所有可能的项目组合 AND reagent_items。

例如，如果我们有两个项目，并且（这两个项目的）所有项目都只有一种定价方法，那么将有 4 种不同的组合：

2 个来自 items
items (item[0]) 的第一个默认项目和 getPricing 的所有 reagent_items for item[1]
来自 items (item[1]) 的第二个默认项目和来自 getPricing 的所有 reagent_items for item[0]
both reagent_items from getPricing for both default items

I literally can't push reagent items to items (or remove item from items) array, because items can be the same (include each other) Instead of it, I am using my own Array.prototype.method for adding/removal items from items array. It does just the same as push/slice but in more elegant way, manipulating with id and quantity fields.

实际问题出在arrays.length和for ... loop字段。

当我们评估默认的笛卡尔积时，我们在 array.length 及其元素之前就知道了。但在我的情况下，我应该 getPricing 每个项目，然后接收方法数组..

架构：

就像：

    Default:        I_1       I_2        ...   N
                   /   \     /   \            / \
Get Pricing:     [I_A, I_B][I_B, I_C]     [IN_J, IN_K],
                                        [IN_Y, IN_X, IN_Z],

所以这不是要查找：Cartesian([I_A, I_B],[I_B, I_C])，而是要查找：

I_1 + I_2
I_1 + (I_B, I_C)
(I_A, I_B) + I_2
(I_A, I_B) + (I_B, I_C)
...

所以默认项目包括彼此及其 reagent_items 并且很容易找到两个项目的所有组合，但是当它变成 3+..

我现在的伪代码：

/* inside async*/
...
let ArrayOfPricing = [] //length 2, where each Array represent Array of `pricing` for each item
Promise.all(items.map(async item => {
   const itemPricing = await getPricing(item.id);
   ArrayOfPricing.push(itemPricing );
})

/**And what's next? **/
for (let item of items) {

}

所以我不明白在这个阶段我接下来应该做什么。

我应该 loop/iterate 每个项目吗？但如果是这样，即使我迭代每个项目 one-by-one 和 change/remove 并添加它的 reagent_items （对于每个定价）我仍然不会更改数组中的下一个 item/element items 的长度超过 2，那么我不会收到所有组合，它会像：

for items
   ↓
  item[1] → for pricing
               → for reagent_items 
                      ↓
               replace item[1] for all reagent_item

  item[2] /** they are still there, but I need iterate over it's pricing , too **/
  item[3]

或者我可以通过查找 items 长度和所有 pricing 长度来计算所有可能的组合，然后形成并清空具有固定长度的新数组并推送到所有组合。但是，如果我用 for loop 迭代它以进行推送...我应该合并项目，它将是 for loop, inside for loop, inside for .. loop..

所以老实说我没有想法。我不要求代替我编写完整的工作代码，而是为我指出走出这个循环的出路。如何获得每个项目的每个组合以及其中的 "baby-items"？那我应该使用多少个周期？如果有任何有用的 idea/pseudocode/post link 可以帮助我处理此案，我将不胜感激。我也来了，会检查下面所有的评论和答案。

UPD a simple version of «from what I get, to what I want»

来自这个：

[ 
   {
      field: "original, can be cloned for every combination", 
      items: 
         [
            {id: 1, quantity: 2},
            {id: 2, quantity: 3} 
         ]
    }
]

至：

[ 
   {
      field: "original", 
      items: 
         [
            {id: 1, quantity: 2},
            {id: 2, quantity: 3} 
         ]
    },
   {
      field: "combination1", 
      items: 
         [
            {id: 11, quantity: 1}, //from getPricing(item[0])
            {id: 12, quantity: 1}, //from getPricing(item[0])
            {id: 2, quantity: 3} 
         ]
    },
   {
      field: "combination2", 
      items: 
         [
            {id: 1, quantity: 2},
            {id: 22, quantity: 3} //from getPricing(item[1])
            {id: 23, quantity: 3} //from getPricing(item[1])
         ]
    },
   {
      field: "combination3", 
      items: 
         [
            {id: 11, quantity: 1}, //from getPricing(item[0])
            {id: 12, quantity: 1}, //from getPricing(item[0])
            {id: 22, quantity: 3} //from getPricing(item[1])
            {id: 23, quantity: 3} //from getPricing(item[
         ]
    }
    //can be any length according to getPricing of every item, and I modify original array, but we could create a new one.
]

Answer 1

正如我所承诺的，我已经找到了我的问题的解决方案，我想与 Whosebug 社区分享它。

伪代码：

let array = [ 
   {
      field: "original, can be cloned for every combination", 
      items: 
         [
            {id: 1, quantity: 2},
            {id: 2, quantity: 3} 
         ]
    }
]


for (let element of array) {
    let MethodsCombinations = [];
    for await (let forCombinations of element.items.map((item, i) => {
        return getMethod(item.id) //get Method for each item)
    })) {
        MethodsCombinations.push(forCombinations)
    }
    /* Cartesian product */
     let vanilla_CartesianProduct = MethodsCombinations.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
    /* Return array of arrays, with objects inside like default array */ 
    /**
    * Other logic with two for loops and merging all the combinations and quantities 
    * with (my own) modified Array.prototype.addItemToArray
    */

}

我非常感谢这个 Nina Scholz's answer and her awesome Whosebug 个人资料提供了关于 combinations/permutations 的所有答案并提供了支持。

multi-dimentonal objects 数组中的笛卡尔积（所有组合），长度灵活

Cartesian product (all combinations) in array of multi-dimentonal objects with flexible length

javascript

arrays

node.js

combinatorics

cartesian-product

笛卡尔积问题：