Determining The Right Combination
Solution 1:
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
- Mathematica.SE: finding all partitions of a set
- How can I maximally partition a set?
- Generating the Partitions of a Set (in C)
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
Solution 2:
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().
Solution 3:
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.
Post a Comment for "Determining The Right Combination"