4

我有一个使用递归函数输出数组所有排列的方法:

    /// <summary>
    /// Yields a sequence of all permutations in lexical order
    /// </summary>
    /// <typeparam name="T">Type of item in the input sequence</typeparam>
    /// <param name="input">The initial sequence</param>
    /// <returns>A sequence of all permutations in lexical order</returns>
    public IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> input) 
    {
        var list = input.ToList();
        list.Sort(); // into lexical order

        if (list.Count > 2)
        {
            foreach (var item in list)
            {
                var itemArray = new[] {item};
                T[] otherItems = list.Except(itemArray).ToArray();
                foreach (var permutation in Permute(otherItems))
                    yield return itemArray.Concat(permutation).ToArray();
            }
        }
        else 
        {
            yield return new[] {list[0], list[1]};
            yield return new[] {list[1], list[0]};
        }
    }

但是,当我在 NUnit 测试中运行此函数时,它终止的时间比我认为的要早得多:

    [Test]
    public void Can_print_all_permutations()
    {
        foreach (var p in Permute("123456789"))
        {
            Console.WriteLine(new string(p.ToArray()));
        }
    }

这是测试打印的最后几行(出于发布目的,我用逗号分隔它们):

349527816、349527861、349528167、349528176、349528617、3

突然终止让我认为控制台的缓冲和刷新是问题的一个组成部分,但应该打印的最后一行是 987654321,所以我觉得循环提前终止了。

如果我在循环中包含一个计算,它会更早终止(在 24... 范围内)。

我的实现中有什么东西可以解释这种行为吗?我在推动堆栈的极限吗?

4

1 回答 1

5

您使用的最有可能的测试基础设施有某种“测试运行的最长时间”限制。枚举所有排列确实需要大量时间。

于 2012-12-20T20:16:12.040 回答