2012-11-07 54 views
0

努力編寫代碼......迷失在循環中。確定正確的組合

我到了那裏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: '#' } 
] 
+0

你是什麼意思「*使用所有元素的最低量*」 - 它是一個奇數據結構的[揹包問題](http://en.wikipedia.org/wiki/Knapsack_problem)?你爲什麼要查找與所有元素相結合的元素總和而不是最低的元素?你會在第三個例子中尋找什麼(因爲沒有這樣的元素,我們不能建立一個總和)? – Bergi

+0

@Bergi - 用更多的例子更新了這個問題......這是否澄清了它? – timborden

+1

我認爲是的,是的。 – Bergi

回答

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。如要進一步瞭解,我發現

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]組合:-)

注意,這些可能不是唯一的解決方案,因爲只有第一許多可能的最小值發現

+0

令人驚歎! @Bergi,你救了我的命...謝謝! – timborden

+0

我覺得它受到了挑戰:-)很高興它有效 – Bergi

0
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()

0

好的..這可能是一種選擇,但因爲我不知道什麼是「最佳組合」的條款,我不能再減少它。

以下代碼應該產生一個包含每個元素作爲對象的對象。然後每個元素對象將包含每個唯一數量的另一個對象(從低到高)。然後金額對象包含該金額可能的組合。

即。容器對象(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 

希望這有助於 - 順便說一句:空量是原始的元素量。