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