如何有效地产生所有的组合（在所有深度），其总和是在指定的范围内 [英] How to efficiently generate all combinations (at all depths) whose sum is within a specified range

问题描述

假设你有一组值（的 1 ， 1 ， 1 ， 12 ， 12 ， 16 ），你会怎么生成所有可能的组合（不重复），其总和为predefined范围内 [最小值，最大值] 。例如，这里是（全部深度）具有与 13 A系列和所有的组合 17 ：

Suppose you have a set of values (1,1,1,12,12,16) how would you generate all possible combinations (without repetition) whose sum is within a predefined range [min,max]. For example, here are all the combinations (of all depths) that have a range between 13 and 17:

1 12

1 1 12

1 1 1 12

16

1 16

这假设值相同的每个产品没有区别，所以你不必 1 12 在最终的输出。蛮力是可能的，但在情况下的物品的数量大时，组合在所有深度的数目是天文数字。在上面的例子中，有（3 + 1）*（2 + 1）*（1 + 1）=在所有深度24的组合。因此，总的组合是任何给定值的项目数的乘积+ 1。当然，我们可以在逻辑上扔出去的组合，其部分之和大于最大值（例如设置的数量庞大16 12 已经超过了最大值更大17 ，所以跳过任何组合的有一个 16 和 12 在其中）。

This assumes that each item of the same value is indistinguishable, so you don't have three results of 1 12 in the final output. Brute force is possible, but in situations where the number of items is large, the number of combinations at all depths is astronomical. In the example above, there are (3 + 1) * (2 + 1) * (1 + 1) = 24 combinations at all depths. Thus, the total combinations is the product of the number of items of any given value + 1. Of course we can logically throw out huge number of combinations whose partial sum is greater than the max value (e.g. the set 16 12 is already bigger than the max value of 17, so skip any combinations that have a 16 and 12 in them).

我本来以为我可以转换输入数组分成两个数组，并增加他们有点像里程表。但我得到完全停留在这个递归算法，打破早。有什么建议？

I originally thought I could convert the input array into two arrays and increment them kind of like an odometer. But I am getting completely stuck on this recursive algorithm that breaks early. Any suggestions?

{
    int uniqueValues = 3;
    int[] maxCounts = new int[uniqueValues];
    int[] values = new int[uniqueValues];

    // easy code to bin the data, just hardcoding for example
    maxCounts[0] = 3;
    values[0] = 1;
    maxCounts[1] = 2;
    values[1] = 12;
    maxCounts[2] = 1;
    values[2] = 16;

    GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}

private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    if (index >= maxValues.Length)
    {
        return;
    }

    while (currentCombo[index] < maxValues[index])
    {
        currentValue += values[index];

        if (currentValue> max)
        {                   
            return;
        }

        currentCombo[index]++;

        if (currentValue< min)
        {                    
            GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            results.Add((int[])currentCombo.Clone());
        }
    }
}

修改

的整数值都只是为了演示。它可以是具有某种数值的任何对象（ INT ，双，浮，等...）

The integer values are just for demonstration. It can be any object that has a some sort of numerical value (int, double, float, etc...)

通常只会有少数唯一值（〜10左右），但可以有几千总笔数。

Typically there will only be a handful of unique values (~10 or so) but there can be several thousands total items.

推荐答案

切换的主要呼吁：

GenerateCombinationsHelper2(new List<int[]>(), 13, 17, 0, maxCounts, new int[3], values);

和再增加code：

private void GenerateCombinationsHelper2(List<int[]> results, int min, int max, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    int max_count = Math.Min((int)Math.Ceiling((double)max / values[index]), maxValues[index]);

    for(int count = 0; count <= max_count; count++)
    {
        currentCombo[index] = count;
        if(index < currentCombo.Length - 1)
        {
            GenerateCombinationsHelper2(results, min, max, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            int sum = Sum(currentCombo, values);
            if(sum >= min && sum <= max)
            {
                int[] copy = new int[currentCombo.Length];
                Array.Copy(currentCombo, copy, copy.Length);
                results.Add(copy);
            }
        }
    }
}

private static int Sum(int[] combo, int[] values)
{
    int sum = 0;
    for(int i = 0; i < combo.Length; i++)
    {
        sum += combo[i] * values[i];
    }
    return sum;
}

它返回5有效答案。

It returns the 5 valid answers.

这篇关于如何有效地产生所有的组合（在所有深度），其总和是在指定的范围内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！