使用排列和递归时性能有限

Question

我正在编写一个程序来计算最长连胜概率，并使用递归来获得所有不同的可能场景。这是我正在做的编码挑战：https://open.kattis.com/problems/winningstreak

我注意到，由于递归，当涉及到更大的输入时，我拥有的置换函数并不是最有效的。一个示例输入是 3，它会将以下内容添加到 matches 数组中： 000, 010, 001, 011, 100,110,101,111

public static void Permutations(string text, int numberOfGames,     List<String> matches)
    {
        if (numberOfGames > 0)
            for (int j = 0; j < 2; j++)
                Permutations(text + j.ToString(), numberOfGames - 1, matches);
        else
        {
            matches.Add(text.ToString());
        }

    }

我的问题在于较大的输入（示例 500），因为这会导致我的程序崩溃并引发错误：垃圾收集器无法为主要堆部分分配 16384 字节的内存。有没有其他方法可以改进此递归，使其在更大的输入上运行得更好？

谢谢大家！

Answer 1

My problem lies with larger inputs (example 500)

您的程序试图生成一个包含 2⁵⁰⁰ 个字符串的列表。

宇宙中大约有2²⁶⁷个原子。

我发现你运行内存不足并不奇怪。

为您的问题找到更聪明的解决方案。

记住，问题不是"enumerate all possible combinations of games"。问题是推导出最长连胜长度的期望值。当组合数量变大时，生成所有可能的组合并求和每个组合中最长连胜的长度是行不通的。

还要记住，问题的陈述是结果 必须在精确结果 的某个分数之内。它不一定是准确的结果。在处理这样的谜题时使用元推理：提出谜题的人可能不会放松问题，除非你可以利用它。

这是否让您对如何解决问题有了一些了解？

如果您需要更多提示和见解，请先阅读以下内容：

http://gato-docs.its.txstate.edu/mathworks/DistributionOfLongestRun.pdf

使用排列和递归时性能有限

Limited performance with use of permutation and recursion

c#

recursion

permutation

repeat