Most likely test infrastructure you are using have some sort of "maximum time for test to run" restriction. Enumerating all permutations does take non-trivial amount of time.
Early termination of recursive iterator block method
-
11-12-2021 - |
Question
I have a method that outputs all the permutations of an array using a recursive function:
/// <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]};
}
}
However, when I run this function in an NUnit test, it terminates far earlier than I think it should:
[Test]
public void Can_print_all_permutations()
{
foreach (var p in Permute("123456789"))
{
Console.WriteLine(new string(p.ToArray()));
}
}
Here's the last lines printed by the test (I separated them by commas for posting purposes):
349527816, 349527861, 349528167, 349528176, 349528617, 3
The abrupt termination makes me think that buffering and flushing by the console is a component of the issue, but the last line that should be printed is 987654321, so I feel like the loop is terminating early.
If I include a calculation in the loop, it terminates even earlier (in the 24... range).
Is there something in my implementation that explains this behavior? Am I pushing the limits of the stack?
Solution