Generate combination of products given a total price limit

Question

I have an array of products id, and 2 arrays with product id in key and price and unique flag in values.

I would like to have all unique combinations of products under a given total limit price :

a product could be several times in combination, except if it is flagged as unique
combination should be sorted by product id
a valid combination is one to the which we can't add product

Sample:

products = [1, 2, 3];

productPrices = {1:10, 2:15, 3:10};

productUnique = {1:true, 2:false, 3:false};

limitPrice = 40;

expected result = [[1,2,2],[1,2,3],[1,3,3,3],[2,2,3],[2,3,3],[3,3,3,3]];

How can I obtain this result in javascript if possible ? Thanks for the help.

@Mohammad, a unique product can be used in any combination but only one time per combination — Julien Maillard, Jan 28 '18 at 20:02

trincot · Accepted Answer · 2018-01-30T16:53:19.277

I would suggest another format for your input, so it is a single array of objects, where each of those objects has an id, price and unique property.

Then with that array of objects and the limit price, use recursion to select at each level of recursion a product to be added to a series of products until none can be added. At that time add the selected product list to a results array.

When selecting a product, determine which products can still be selected in the next level of recursion: when a unique product was selected, then don't pass that on as a selection possibility to the next level.

To avoid duplicates, once a product is no longer selected from, don't come back to it at deeper recursion levels; so pass on a shorter product list in recursion when it is decided not to pick the same product again. The recursion ends when the cheapest, still available product is more expensive than the amount that is still available.

Here is a snippet:

function intoOne(products, productPrices, productUnique) {
    return products.map( (id) => ({
        id,
        price: productPrices[id],
        unique: productUnique[id]
    }));
}

function combinations(products, limitPrice) {
    const results = [];
    
    function recurse(sel, products, minPrice, maxPrice) {
        products = products.filter(p => p.price <= maxPrice);
        if (!products.length && minPrice > maxPrice) return results.push(sel);
        products.forEach( (p, i) => {
            recurse(sel.concat(p.id), products.slice(i+p.unique), 
                    minPrice, maxPrice-p.price);
            minPrice = Math.min(minPrice, p.price);
        });
    }
    
    recurse([], products, limitPrice, limitPrice);
    return results;
}

var products = [1, 2, 3],
    productPrices = {1:10, 2:15, 3:10},
    productUnique = {1:true, 2:false, 3:false},
    limitPrice = 40;
// Combine product characteristics in more suitable structure
products = intoOne(products, productPrices, productUnique);
// Call main algorithm
var result = combinations(products, limitPrice);
console.log(JSON.stringify(result));

Thanks for the quick response, this solution works fine with the given sample, but with an other set of data it produce unattended results. For example with prices = {1:2, 2:4, 3:2} and unique = {1:false, 2:false, 3:true} and limitPrice = 10, it returns [[1,1,1,1,1],[1,1,1,1,3],[1,1,1,2],**[1,1,1,3]**,[1,1,2,3],**[1,1,3]**,[1,2,2],**[1,2,3]**,**[1,3]**,[2,2,3],**[2,3]**,**[3]**]. I would like to remove the values in bold froms results. — Julien Maillard, Jan 28 '18 at 23:46
Indeed, I have now updated the script to only produce a result when the price of the cheapest product that is still available is too high for the available amount. — trincot, Jan 29 '18 at 08:15
Thanks, it's exactly what i want and the solution is very efficient and simple once we have the solution under the eyes :) ! — Julien Maillard, Jan 30 '18 at 16:41

Nina Scholz · Answer 2 · 2018-01-28T20:51:00.187

You could take an iterative and recursive approach by checking the sum, length and unique parameter for next call of the same function with changed index or temporary items.

If the sum is smaller than the limit, the temporary result is added to the result set.

function iter(index, temp) {
    var product = products[index],
        sum = temp.reduce((s, k) => s + prices[k], 0);

    if (sum + prices[product] > limit) {
        result.push(temp);
        return;
    }

    if (!unique[product] || temp[temp.length - 1] !== product) {
        iter(index, temp.concat(product));
    }

    if (index + 1 < products.length) {
        iter(index + 1, temp);
    }
}

var products = [1, 2, 3],
    prices = { 1: 10, 2: 15, 3: 10 },
    unique = { 1: true, 2: false, 3: false },
    limit = 40,
    result = [];

iter(0, []);

console.log(JSON.stringify(result));

Generate combination of products given a total price limit

2 Answers2

Linked