确定正确的组合 [英] Determining the right combination

查看：58
本文介绍了确定正确的组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

努力编写代码...在循环中迷路了.

Struggling to write the code...getting lost in the loops.

我有2个数据集，例如:

I've got there 2 data sets, for example:

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

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

I'm looking for the lowest amount using all the elements.

答案是329 + 328.

The answer is 329 + 328.

此处包含3个元素，例如:

Here it is, with 3 elements, for example:

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 ....但是我不知道如何通过代码到达那里.

The answer here is 314 + 313 + 312....but I don't know how to get there with code.

当元素可能无法全部组合在一起时，事情就会变得更加复杂，例如:

Things get a more complicated with more elements, when they may not all go together in combination, for example:

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

关于如何解决此问题的任何想法?

Any ideas on how to approach this?

(对不起，解释和解决同样困难)

(sorry, it's just as tough to explain as it is to solve)

进行澄清

这是一个抽象的例子:

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

我想知道产生最小值的是什么，

I want to know what produces the lowest value, the calculations are:

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

然后，我需要根据元素和具有最佳组合的elements_in_combination构建一个数组，例如:

Then I need to build an array from the elements and the elements_in_combination that has the best combination, for example:

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

推荐答案

确定.检查此脚本:

// 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难题，不易解决.三个元素(问题中的五个组合)的简单处理变得越来越复杂，对于六个元素，您已经具有203种可能性(

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

那么，这就是您的结果！它在amount属性中包含所需的总和，在set属性中包含已使用的组合键集.

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.J3e.E0C)+ 311(21.U2duHWiX.J3e.E0C)+ 312(21.U2duHWiX.P1y.E0C)-a 组合:-)

请注意，这些可能不是唯一的解决方案，因为在许多可能的极小值中只有第一个找到了

Note that these may not be the sole solutions, as there is only the first of many possible minima found

这篇关于确定正确的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
前端开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆