c# - 如何高效生成总和在指定范围内的所有组合(在所有深度)

Question

假设您有一组值 (1,1,1,12, 12,16)如何生成所有可能的组合(不重复)，其总和在预定义范围[min,max]内。例如，以下是范围在 13 和 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 的任何组合> 在其中)。

我最初认为我可以将输入数组转换为两个数组，然后像里程表一样递增它们。但我完全陷入了这种提前崩溃的递归算法中。有什么建议吗？

{
    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、double、float 等)

通常只有少数唯一值(大约 10 个)，但总共可能有数千个项目。

Answer 1

将主调用切换到:

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

然后添加以下代码:

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 个有效答案。