StackOverflowException 当递归算法中的数字很大时。优化？

Question

任务：我需要将一定数量的包裹分发到不同容量的容器中。

每个容量都有限制：最小和最大包裹数。

包裹数量应等于或小于所选容器容量的总和。

容量存储在数据库中。包裹总和由用户提示，可以是小数。

结果应该是每个容器的容器容量集合。结果计数没有限制。

我有一个用 C# 编写的递归解决方案，但它因大包总和的 WhosebugException 而崩溃。

// returns all combinations of capacity max and min values which package sum could include
static IEnumerable<List<int>> GetCombinations(int[] set, int sum, List<int> values)
{
    for (var i = 0; i < set.Length; i++)
    {
        var left = sum - set[i];
        var vals = new List<int>(values);
        vals.Add(set[i]);

        if (left == 0)
        {
            yield return vals;
        }
        else
        {
            int[] possible = set.Where(n => n <= sum).ToArray();
            if (possible.Length > 0)
            {
                foreach (var s in GetCombinations(possible, left, vals))
                {
                    yield return s;
                }
            }
        }
    }
}

调用代码，其中 packageCapacities 包含属性 Count（实际上是 MaxCount）和 MinCount：

var allCapacityValues = packageCapacities
    .SelectMany(x => Enumerable.Range((int)x.MinCount, (int)x.Count - (int)x.MinCount + 1))
    .OrderByDescending(x => x)
    .ToArray();
// gets first combination, sort numbers in it and distinct it
var combination = GetCombinations(allCapacityValues, (int)Math.Ceiling(contentData.FactCount), new List<int>())
    .Select(x => x.OrderByDescending(o => o))
    .Distinct(new EnumerableComparer<int>())
    .FirstOrDefault();

其中有两个容量和 13 的总和，分配到 3 个容器大小。

可重现代码：

using System;
using System.Collections.Generic;
using System.Linq;

namespace Data.Services
{
    public class ContainerGenerationService1
    {
        public void GenerateContainersWorks()
        {
            int capacity1Min = 4;
            int capacity1Max = 5;
            int capacity2Min = 2;
            int capacity2Max = 2;
            int[] set = Enumerable.Range(capacity1Min, capacity1Max - capacity1Min + 1)
                .Concat(Enumerable.Range(capacity2Min, capacity2Max - capacity2Min + 1))
                .ToArray();
            int sum = 13;

            var combination = GetCombinations(set, sum, new List<int>())
              .Select(x => x.OrderByDescending(o => o))
              .Distinct(new EnumerableComparer<int>())
              .FirstOrDefault();
        }

        public void GenerateContainersFails()
        {
            int capacity1Min = 3;
            int capacity1Max = 9;
            int[] set = Enumerable.Range(capacity1Min, capacity1Max - capacity1Min + 1).ToArray();
            int sum = 999999;

            var combination = GetCombinations(set, sum, new List<int>())
              .Select(x => x.OrderByDescending(o => o))
              .Distinct(new EnumerableComparer<int>())
              .FirstOrDefault();
        }


        static IEnumerable<List<int>> GetCombinations(int[] set, int sum, List<int> values)
        {
            for (var i = 0; i < set.Length; i++)
            {
                var left = sum - set[i];
                var vals = new List<int>(values);
                vals.Add(set[i]);

                if (left == 0)
                {
                    yield return vals;
                }
                else
                {
                    int[] possible = set.Where(n => n <= sum).ToArray();
                    if (possible.Length > 0)
                    {
                        foreach (var s in GetCombinations(possible, left, vals))
                        {
                            yield return s;
                        }
                    }
                }
            }
        }

        class EnumerableComparer<T> : IEqualityComparer<IEnumerable<T>> where T : IComparable<T>
        {
            public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
            {
                if (first == second)
                    return true;
                if ((first == null) || (second == null))
                    return false;

                return new HashSet<T>(first).SetEquals(second);
            }

            public int GetHashCode(IEnumerable<T> enumerable)
            {
                return enumerable.OrderBy(x => x)
                  .Aggregate(1, (current, val) => current + val.GetHashCode());
            }
        }
    }
}

调用代码：

var svc = new ContainerGenerationService1();
svc.GenerateContainersWorks(); // works
svc.GenerateContainersFails(); // fails with WhosebugException

Answer 1

堆栈溢出绝不是您的代码的唯一问题，但让我们从这里开始。 GetCombinations 递归调用自身。当你得到几十万的调用深度时，你运行出栈。在这种情况下你不能使用系统堆栈，你需要更大的数据存储。

您在这里只寻找一种解决方案，但代码显然是为了 return 所有不同的集合而编写的。但是你应该重新考虑这种方法。您生成所有变体，然后选择独特的集合并丢弃其余的。这是非常昂贵的。就像，差几个数量级。您应该直接生成不同的集合。比如，如果你有数字 6，下一个数字可以是 6 或 5 或 4，但不能是 7。

下一个大问题是无解的情况。如果存在，您可能会很快找到一些解决方案。但如果没有，您将循环使用多种组合。您可以使用动态规划来解决这个问题。它会告诉您哪些数量对您拥有的容器有效，哪些不是。你可以用它来进一步提高递归的效率。

每次从函数 return 中创建新的 List。这是安全的方法。但是您通常可以 return 同一个列表并对其进行修改。对于像 GetCombinations(...).Count() 这样的情况，它更有效。让我们把它们放在一起

static IEnumerable<List<int>> GetCombinations(int[] set, int sum)
{
    var orderedSet = set.Distinct().OrderByDescending(o => o).ToArray();

    bool[] valid = new bool[sum + 1];
    valid[0] = true;
    for (int i = 0; i < sum; ++i)
    {
        if (valid[i])
        {
            for (int j = 0; j < orderedSet.Length; ++j)
            {
                int next = i + orderedSet[j];
                if (next < valid.Length)
                {
                    valid[next] = true;
                }
            }
        }
    }

    if (!valid[sum])
    {
        return new List<int>[0]; //no solution
    }

    return GetCombinationsRecurse(orderedSet, sum, new List<int>(), valid, 0);
    //return GetCombinationsNoRecurse(orderedSet, sum, valid);
}      

static IEnumerable<List<int>> GetCombinationsRecurse(int[] set, int sum, 
    List<int> values, bool[] valid, int setIterator)
{
    for (var i = setIterator; i < set.Length; i++)
    {
        var left = sum - set[i];
        if (left < 0 || !valid[left])
        {
            continue;
        }

        values.Add(set[i]);

        if (left == 0)
        {
            yield return values;
        }
        else
        {
            foreach (var s in GetCombinationsRecurse(set, left, values, valid, i))
            {
                yield return s;
            }
        }
        values.RemoveAt(values.Count - 1);
    }
}

我在这里给出了递归版本，因为它与您的原始代码匹配并且更容易理解。但是大数的堆栈溢出显然仍然存在。递归函数总是可以重写为非递归版本。您需要使用一些数据结构而不是系统堆栈。堆栈，数组或其他任何东西。但是往往不好看

static IEnumerable<List<int>> GetCombinationsNoRecurse(int[] set, int sum, bool[] valid)
{
    List<int> sums = new List<int>() { 0 };
    List<int> setIterators = new List<int>() { 0 };
    int iter = 0;
    List<int> values = new List<int>() { set[iter] };

    while (true)
    {
        int actSum = sums[iter] + values[iter];
        int left = sum - actSum;
        if (left == 0)
        {
            yield return values;
        }

        if (left <= 0 || !valid[left])
        {
            while (++setIterators[iter] >= set.Length)
            {
                if (--iter < 0) { yield break; }
                values.RemoveAt(values.Count - 1);
            }
            values[iter] = set[setIterators[iter]];
            continue;
        }

        { // left > 0
            if (sums.Count > iter + 1)
            {
                sums[iter + 1] = actSum;
                setIterators[iter + 1] = setIterators[iter];
            }
            else
            {
                sums.Add(actSum);
                setIterators.Add(setIterators[iter]);
            }

            values.Add(values[iter]);
            iter++;
        }
    }
}

StackOverflowException 当递归算法中的数字很大时。优化？

StackOverflowException when big numbers in recursive algorithm. Optimization?

c#

recursion

sum

largenumber