올바른 조합 결정

Question

코드를 작성하는 데 어려움을 겪고 있습니다. 루프에서 길을 잃고 있습니다.

나는 예를 들어,이 두 데이터 세트를 가지고 : 나는 모든 요소를 ​​사용하여 가장 낮은 금액을 찾고 있어요

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

.

대답은 예를 들어, 3 개 소자와, 여기에 329 + 328

그것이이다

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

내가 무엇을 알고 싶어 여기에 추상적 인 예입니다

을 명확히하기 위해 :

는

편집을 (죄송합니다, 그것은 해결하기로 설명 할만큼 힘든) 가장 낮은 값을 산출하면 계산은 다음과 같습니다.

,210

는 그럼 예를 들어 요소에서 배열과 최고의 조합을 가지고 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 어려운 문제이며 쉽게 해결할 수 없습니다. 세 가지 요소 (귀하의 질문에 다섯 개 가지 조합) 이미 (Bell numbers을 203 가능성이 6 개 요소, 점점 더 복잡해진다. 추가 읽기를 들어, 내가 찾은 쉽게 무엇

• Mathematica.SE: finding all partitions of a set
• How can I maximally partition a set?
  :이 반복적으로, 캐싱 결과를 해결할 수 있도록 최소 값을 받고,

OK (C에서)

// 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.EOC) + 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; 
} 

이 array_equal()을 구현하는 방법에 대한 this question를 참조하십시오.

Answer 3

ok ..이 옵션이 될 수도 있지만 "최상의 조합"에 대한 용어가 무엇인지 전혀 알지 못하기 때문에 더 이상 줄일 수 없습니다.

다음 코드는 각 요소를 개체로 포함하는 개체를 생성해야합니다. 각 요소 객체에는 고유 한 양 (낮은 값에서 높음 값)마다 다른 객체가 포함됩니다. 금액 오브젝트에는 해당 금액에 대해 가능한 조합이 들어 있습니다.

즉. 컨테이너 개체 (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 

희망 - BTW : 널 양이 원래 요소의 양이다.