Determining the right combination

Question

Struggling to write the code...getting lost in the loops.

I've got there 2 data sets, for example:

var elements = [
        {"id":"21.U2duHWiX.0zu.E0C","amount":"345"},
        {"id":"21.U2duHWiX.A5q.E0C","amount":"344"}
    ]

var elements_in_combination = [
    {"id":"21.U2duHWiX.0zu.E0C","amount":"329","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"328","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C"]},
]

I'm looking for the lowest amount using all the elements.

The answer is 329 + 328.

Here it is, with 3 elements, for example:

var elements = [
        {"id":"21.U2duHWiX.0zu.E0C","amount":"345"},
        {"id":"21.U2duHWiX.A5q.E0C","amount":"344"},
        {"id":"21.U2duHWiX.P1y.E0C","amount":"343"}
    ]

var elements_in_combination = [
    {"id":"21.U2duHWiX.0zu.E0C","amount":"329","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"328","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"329","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"327","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"328","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"327","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"314","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"313","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"312","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]}
]

The answer here is 314 + 313 + 312....but I don't know how to get there with code.

Things get a more complicated with more elements, when they may not all go together in combination, for example:

var elements = [
    {"id":"21.U2duHWiX.0zu.E0C","amount":"345"},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"344"},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"342"},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"343"}
]

var elements_in_combination = [
    {"id":"21.U2duHWiX.0zu.E0C","amount":"329","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"328","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"329","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"326","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"329","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"327","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"328","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"326","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"328","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"327","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"326","combination":["21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"327","combination":["21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"314","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"313","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"311","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"314","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"313","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"312","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.A5q.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.0zu.E0C","amount":"314","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"311","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"312","combination":["21.U2duHWiX.0zu.E0C","21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.A5q.E0C","amount":"313","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.J3e.E0C","amount":"311","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]},
    {"id":"21.U2duHWiX.P1y.E0C","amount":"312","combination":["21.U2duHWiX.A5q.E0C","21.U2duHWiX.J3e.E0C","21.U2duHWiX.P1y.E0C"]}
]

Any ideas on how to approach this?

(sorry, it's just as tough to explain as it is to solve)

EDIT: to clarify

Here's an abstract example:

var elements = [ 
    { id: A, value: '#' },
    { id: B, value: '#' },
    { id: C, value: '#' }
]

var elements_in_combination = [
    { id: A, value: '#', combinations: [A, B] },
    { id: B, value: '#', combinations: [A, B] },
    { id: A, value: '#', combinations: [A, C] },
    { id: C, value: '#', combinations: [A, C] },
    { id: B, value: '#', combinations: [B, C] }, 
    { id: C, value: '#', combinations: [B, C] },
    { id: A, value: '#', combinations: [A, B, C] },
    { id: B, value: '#', combinations: [A, B, C] },
    { id: C, value: '#', combinations: [A, B, C] },
]

I want to know what produces the lowest value, the calculations are:

[A, B, C] = '##'
or
[A, B] + C = '##'
or
[A, C] + B = '##'
or
A + [B, C] = '##'
or
A + B + C = '##'

Then I need to build an array from the elements and the elements_in_combination that has the best combination, for example:

var elements = [ 
    { id: A, value: '#', combinations: [A, B] },
    { id: B, value: '#', combinations: [A, B] },
    { id: C, value: '#' }
]

What do you mean by "*lowest amount using all the elements*" - is it the [knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem) with an odd datastructure? Why do you look for the sum of the amounts of elements which are combined with all of them, instead of the lowest of them? And what are you going to look for in the third example (as there are no such elements, we can't build a sum)??? — Bergi, Nov 07 '12 at 21:22
@Bergi - updated the question with more examples...does that clarify it? — timborden, Nov 07 '12 at 21:54

score 1 · Accepted Answer · edited May 23 '17 at 12:25

OK. Check this script:

// this part is only needed if your ids are arbitrary, and can contain the join-character
// if not, you could replace this by the identity function
var count = 0, numericids = {};
function getNumericId(id) {
    return id in numericids ? numericids[id] : numericids[id] = count++;
}

// returns the same (reversible) id for all similiar [unsorted] key combinations
function id(keys) {
    return keys.map(getNumericId).sort().join('-');
    // you might remove the getNumericId part if distinct without
}

// now, build a map that holds the summed amount for each single (sub)combination
var amounts = {};
function add(amount, keys) {
    var key = id (keys);
    if (key in amounts)
        amounts[key] += amount;
    else
        amounts[key] = amount;
}
for (var i=0; i<elements.length; i++) // each element is a single combination
    add(Number(elements[i].amount), [elements[i].id]);
for (var i=0; i<elements_in_combination.length; i++)
    add(Number(elements_in_combination[i].amount), elements_in_combination[i].combination);
// so we have the amounts in a good accessible structure now

Next, we will need to find all partitions of a set. Wow. This is an NP-hard problem and not easily solvable. What was easy for three elements (the five combinations in your question) gets more and more complicated, for 6 elements you already have 203 possibilities (Bell numbers. For further reading, I've found

OK, let's solve this recursively, caching results and getting the minimum value:

// first, get the set for which we want to determine the result:
var initialset = elements.map(function(el){return getNumericId(el.id);}).sort();
// set up a cache for minimum value results:
var cache = {};

function partition(set) {
// returns an array of all partitionings into two parts
    var results = [[[set[0]],[]]];
    for (var i=1; i<set.length; i++)
        for (var j=0, l=results.length; j<l; j++) {
            // repeat the array with duplicates
            results[j+l] = [results[j][0].slice(),results[j][1].slice()];
            // but while we push to the first part in the first half
            results[ j ][0].push(set[i]);
            // we push to the second part in the second half
            results[j+l][1].push(set[i]);
        }
    return results;
}

function getMin(set) {
    var key = set.join('-');
    if (key in cache) // quick escape
        return cache[key];
    var result = {amount:Infinity, set:null};
    if (key in amounts) // there is a combination with this
        result = {amount:amounts[key], set:[key]};
    var divisions = partition(set);
    // for all possibilities to divide the set in two parts
    // (unless the first, which is [set, []])
    for (var i=1; i<divisions.length; i++) {
        // get the minimal amounts of both parts
        var first = getMin(divisions[i][0]);
        var second = getMin(divisions[i][1]);
        var sum = first.amount + second.amount;
        if (sum < result.amount) // and find new minima
            result = {amount:sum, set: first.set.concat(second.set)};
    }
    return cache[key] = result;
}
// And now invoke this monster!
if (!initialset.length) throw new Error("When searching for nothing you would find nothing");
var min = getMin(initialset);
cache = null, amounts = null; // and immediately free the memory

So, here is your result! It contains the sum you wanted in the amount property and the used set of combination-keys in the set property.

Building your array of elements is easy now:

var elemArr = [];
function addElem(el, comb) {
    if (min.set.indexOf(id(comb)) >= 0)
         elemArr.push(el);
}
for (var i=0; i<elements.length; i++) // each element is a single combination
    addElem(elements[i], [elements[i].id]);
for (var i=0; i<elements_in_combination.length; i++)
    addElem(elements_in_combination[i], elements_in_combination[i].combination);

return elemArr; // We've done it!

The script returns the correct results for all your examples:

329 (21.U2duHWiX.0zu.E0C) + 328 (21.U2duHWiX.A5q.E0C)
314 (21.U2duHWiX.0zu.E0C) + 313 (21.U2duHWiX.A5q.E0C) + 312 (21.U2duHWiX.P1y.E0C)
344 (21.U2duHWiX.A5q.E0C) + 314 (21.U2duHWiX.0zu.E0C) + 311 (21.U2duHWiX.J3e.E0C) + 312 (21.U2duHWiX.P1y.E0C) - a [B]-[A,C,D] combination :-)

Note that these may not be the sole solutions, as there is only the first of many possible minima found

score 0 · Answer 2 · edited May 23 '17 at 11:46

function find_matches(elements, elements_in_combination) {
    var matches = ();
    var element_ids = ();
    for (var i = 0; i < elements.length; i++) {
        element_ids.push(elements[i].id);
    }
    element_ids.sort();
    for (i = 0; i < elements_in_combination.length; i++) {
        combs = elements_in_combination[i].combination.slice(0).sort();
        if (array_equal(element_ids, combs)) {
            matches.push(elements_in_combination[i].amount;
        }
    }
    return matches;
}

See this question for how to implement array_equal().

logic8 · Answer 3 · 2012-11-08T00:35:52.853

ok.. this might be an option, but because I have no idea what the terms for the "best combination" are, I couldn't reduce it any further.

the following code should produce an object that contains each element as an object. Each element object will then contain another object for each unique amount (from low to high). The amount object then contains the combinations possible for that amount.

ie. container object (finalElements) - element id - order & amounts - combinations:

var finalElements = { };

// sort:
elements_in_combination.sort( eic_sortOnAmmount );

function eic_sortOnAmmount( a, b ) {
    return a.amount - b.amount;
}

// parse the elements array and create an object for each element
// add the initial amount as a key:
for( var i in elements ) {
    finalElements[ elements[i].id ] = { order:[] };
    finalElements[ elements[i].id ][ elements[ i ].amount ] = null;
}

// parse the elements_in_combination array
// if the id matches one of the elements in finalElements
// add its amount and combination
for( var i in elements_in_combination ) {
    if( finalElements.hasOwnProperty( elements_in_combination[ i ].id ) ) {
        if( finalElements[ elements_in_combination[ i ].id ].hasOwnProperty( elements_in_combination[ i ].amount ) ) {
            finalElements[ elements_in_combination[ i ].id ][ elements_in_combination[ i ].amount ].push( elements_in_combination[ i ].combination );
        } else {
            finalElements[ elements_in_combination[ i ].id ].order.push(elements_in_combination[ i ].amount);
            finalElements[ elements_in_combination[ i ].id ][ elements_in_combination[ i ].amount] = [ elements_in_combination[ i ].combination ];
        }
    }
}

example usage:

console.log(finalElements["21.U2duHWiX.0zu.E0C"].order[0]); //produces 314
console.log(finalElements["21.U2duHWiX.0zu.E0C"][finalElements["21.U2duHWiX.0zu.E0C"].order[0]]); // produces the combinations for 314

Hope this helps - btw: the null amount is the original element amount.

Determining the right combination

3 Answers3

Linked