0

There are several questions with answers on StackOverflow which shows how to find Cartesian product for various simple arrays. And a wonderful article on RosettaCode. But I can't find any solution for my problem.

I have an array of object with items, let's call it items:

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

Every item in this array have a pricing/crafting method and we could receive it by request.

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*/]}
]

CARTESIAN PRODUCT PROBLEM:

As you may already understand, according to the answer's title, I want to receive all possible combinations of items AND reagent_items from pricing methods.

For example, if we have two items and all every item (of this 2) have just one pricing method, there will be 4 different combinations:

  1. 2 default items from items
  2. first default item from items (item[0]) and all all reagent_items from getPricing for item[1]
  3. second default item from items (item[1]) and all all reagent_items from getPricing for item[0]
  4. 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.

The actual problem lies in the field of arrays.length and for ... loop.

When we evaluate default Cartesian product we know before the array.length and it's elements. But in my case I should getPricing every items, then receive array of methods..

Schema:

It's like:

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

So it's not about finding: Cartesian([I_A, I_B],[I_B, I_C]) but something like:

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

So default item includes each others and their reagent_items and it's simple to find all combinations of two items, but when it's become 3+..

My current pseudo code for now:

/* 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) {

}

So I can't understand what should I do next, at this stage.

  • Should I loop/iterate every item? But if so, even if I iterate every item one-by-one and change/remove it and add it's reagent_items (for every pricing) I still don't change the next item/element in array of items and it's length more then just 2, then I won't receive all the combinations, it will be like:
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]
  • or I could calculate all possible combinations by looking for items length and all pricing length and then form and empty new array with fixed length and push to all the combinations. But if I iterate over it for push with for loop... I should combine items and it will be for loop, inside for loop, inside for .. loop..

So to be honest I am out of ideas. I don't ask to write full working code instead of me, but to point me the way out of this loop. How to get every combination for every item and "baby-items" inside of it? How many cycles should I use then? I'll be grateful for any useful idea/pseudocode/post link which will help me to deal with this case. I'm also here and will check all the comments and answers below.

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

from this:

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

to:

[ 
   {
      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.
]
11
  • Should the (I_B+I_C) be (I_B,I_C) ? Commented Apr 20, 2020 at 12:11
  • @TedBrownlow Y, I already fixed it Commented Apr 20, 2020 at 12:12
  • 1
    please add an exaple of the wanted result with the given data. Commented Apr 20, 2020 at 12:21
  • 1
    maybe you have a look to this question: stackoverflow.com/q/56972012/1447675 Commented Apr 20, 2020 at 12:24
  • 1
    i have no idea how you get the wanted items. what is the building rule for it? how do you limit the values? Commented Apr 20, 2020 at 14:40

1 Answer 1

0

As I promised, I have found a solution of my problem and I'd like to share it with StackOverflow Community.

Pseudo-code:

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
    */

}

I am very grateful to this Nina Scholz's answer and her awesome StackOverflow profile with all answers about combinations/permutations and for providing a support.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.