确定正确的组合

Question

努力编写代码......迷失在循环中。

我到了那里2的数据集，例如：

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

我正在寻找使用所有元素的最低量。

答案是329 + 328

这与3个元素，例如：

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"]} 
] 

这里答案是314 + 313 + 312 ....但我不不知道如何用代码到达那里。

事情就会有更多的元素更复杂，当他们可能不是所有走在一起的组合，例如：

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"]} 
] 

对如何处理这个任何想法？

（对不起，它只是作为很难解释，因为它是解决）

编辑：澄清

下面是一个抽象的例子：

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

我想知道是什么产生最低值，计算如下：

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

然后，我需要建立从元素的数组，并具有最佳组合elements_in_combination，例如：

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

Answer 1

好的。检查脚本：

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

接下来，我们需要找到所有的partitions of a set。哇。这是一个NP难题，不易解决。什么是容易的三个要素（你的问题中的五个组合）变得越来越复杂，6个元素你已经有了203点的可能性（Bell numbers。如要进一步了解，我发现

• Mathematica.SE: finding all partitions of a set
• How can I maximally partition a set?
• Generating the Partitions of a Set（C语言）

OK，让我们来解决这个递归，缓存结果和获得的最小值：

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

所以，这是你的结果！它包含amount属性中您想要的总数以及set属性中使用的一组组合键。

建立你的元素的数组现在很容易：

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! 

的脚本返回所有的例子正确的结果：

• 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） - 一个[B]-[A,C,D]组合:-)

注意，这些可能不是唯一的解决方案，因为只有第一许多可能的最小值发现

Answer 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; 
} 

见this question如何实施array_equal()。

Answer 3

好的..这可能是一种选择，但因为我不知道什么是“最佳组合”的条款，我不能再减少它。

以下代码应该产生一个包含每个元素作为对象的对象。然后每个元素对象将包含每个唯一数量的另一个对象（从低到高）。然后金额对象包含该金额可能的组合。

即。容器对象（finalElements） - 元素的id - 为了&量 - 的组合：

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 ]; 
     } 
    } 
} 

示例用法：

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 

希望这有助于 - 顺便说一句：空量是原始的元素量。