javascript - 適切な組み合わせの決定

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: '#' }
]

score 1 · Accepted Answer

わかった。このスクリプトを確認してください:

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

次に、セットのすべてのパーティションを見つける必要があります。わお。これは NP 困難な問題であり、簡単には解決できません。3 つの要素 (質問の 5 つの組み合わせ) では簡単だったことが、ますます複雑になり、6 つの要素では既に 203 の可能性があります (ベル数。さらに読むために、私は見つけました

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

多くの可能性のある最小値のうち最初のものしか見つからないため、これらが唯一の解ではないことに注意してください。

score 0 · Accepted Answer

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

score 0 · Accepted Answer

わかりました..これはオプションかもしれませんが、「最良の組み合わせ」の用語が何であるかがわからないため、これ以上減らすことはできませんでした.

次のコードは、各要素をオブジェクトとして含むオブジェクトを生成する必要があります。各要素オブジェクトには、一意の量 (低いものから高いものまで) ごとに別のオブジェクトが含まれます。金額オブジェクトには、その金額で可能な組み合わせが含まれます。

すなわち。コンテナーオブジェクト ( 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

これが役に立てば幸いです-ところで：nullの量は元の要素の量です。

javascript - 適切な組み合わせの決定

3 に答える 3

Related

Reference