Card Combinations

Combinations can be built recursively. Start with an empty combination and add cards from your full deck until you have reached the desired size. That's the first combination. You can then remove the last card in the combination and replace it with the other remaining cards in the deck for the next set of combinations. Once you've tried every card in the last place in the hand, backtrack to the last place but one and replace that card with the next one, then proceed as before. Keep backtracking and trying each card until you're done. Make sense? Probably not as it turns out it's quite hard to explain recursive algorithms. So let's try an example - build all combinations of 2 letters from the set of 4 letters A, B, C and D:

• Start at index 0 and add the first letter:
  [A
• Move on to index 1 and try each remaining letter in turn:
  [A, B] [A, C] [A, D]
• Backtrack to index 0 and try the next letter:
  [B
• Carry on as before trying the remaining letters:
  [B, C] [B, D]
• Backtrack again:
  [C
• And try the remaining letter:
  [C, D]
• Backtrack again:
  [D
• No further letters to try; we're done.

Note that we only use letters after the one we've just added, i.e. when we were on [B we did not then proceed to add A to give [B, A] - that would give us permutations, not combinations.

The C# code for the above would look something like this:

public static IEnumerable<IImmutableSet<Card>> Combinations(IReadOnlyList<Card> source, int combinationSize) =>
    Combinations(source, 5, ImmutableCardSet.Empty, 0);

private static IEnumerable<IImmutableSet<Card>> Combinations(IReadOnlyList<Card> source, int combinationSize, IImmutableSet<Card> currentCombination, int startSourceIndex)
{
    // Reached the desired size; return the combination.
    if (combinationSize == currentCombination.Count)
    {
        yield return currentCombination;
        yield break;
    }

    // Start from the current index in our source. We will add each card in turn from that index onwards to the combination.
    for (var f = startSourceIndex; f < source.Count; f++)
    {
        // Add the card and proceed recursively from the next index to fill up the combination.
        foreach (var result in Combinations(source, combinationSize, currentCombination.Add(source[f]), f + 1))
        {
            yield return result;
        }
    }
}

Whilst that works there is an overhead from recursion. Every recursive calls needs push a stack frame onto the call stack, make the method call and restore the stack afterwards. To avoid this overhead we can make the algorithm iterative by managing the stack aspect ourselves. This should be faster and use less memory, at the cost of more complicated code. Our recursive algorithm has two parameters we need to store on our stack, currentCombination and startSourceIndex, giving us an iterative version that looks something like this:

public static IEnumerable<IReadOnlyCardSet> Iterative_Stack(IReadOnlyList<Card> source, int combinationSize)
{
    // Stack of the current combination and the next index to start with for that combination.
    var stack = new Stack<(ImmutableCardSet CurrentCombination, int StartSourceIndex)>(combinationSize);
    stack.Push((ImmutableCardSet.Empty, 0));

    // Whilst the stack isn't empty we have more cards to process.
    while (stack.Count > 0)
    {
        // Pop the stack to get the next index to process.
        var (combination, startSourceIndex) = stack.Pop();

        // Loop over the remaining cards to add them to the combination.
        while (startSourceIndex < source.Count)
        {
            // Add the next card.
            var toAdd = source[startSourceIndex];
            startSourceIndex++;
            
            // Push the combination and the position of the next card to add onto the stack so we come back to them later.
            stack.Push((combination, startSourceIndex));

            combination = combination.Add(toAdd);
            
            // If we've reached the desired size return the combination.
            if (stack.Count == combinationSize) 
            {
                yield return combination;
                break;
            }
        }
    }
}

So a lot more complex but hopefully quicker. We can test with Benchmark.NET to be sure by generating all 2,598,960 distinct five card hands for each method and comparing:

|    Method |      Mean |    Error |   StdDev | Ratio |      Gen 0 | Allocated |
|---------- |----------:|---------:|---------:|------:|-----------:|----------:|
| Recursive | 218.83 ms | 1.070 ms | 0.948 ms |  1.00 | 55333.3333 |    331 MB |
| Iterative |  51.72 ms | 0.316 ms | 0.280 ms |  0.24 |  9900.0000 |     59 MB |

Yup quite a bit quicker! It also allocates a lot less memory, which is nice. Can we grind out a bit more performance still? There are a few things that might slow the above down:

• .NET's Stack<T> class has a few overheads. For example it tracks a version number so it can give you the dreaded "Collection was modified; enumeration operation may not execute." exception. It also needs to check if a resize is required, but in our case it never is as we have a fixed size. We could therefore replace it with a simple array and an integer to keep track of our position in the array.
• We are storing tuples in our stack, and there will be a small overhead with creating them and dereferencing the items. Instead we could store two arrays, one for the cards and one for the indices.
• We create card sets for incomplete combinations. Instead we could work with the underlying bit indices instead to avoid this overhead, along with any other overheads the sets might add.

Each of these incremental improvements gives us another speed boost:

|                         Method |      Mean |    Error |   StdDev | Ratio | RatioSD |
|------------------------------- |----------:|---------:|---------:|------:|--------:|
|                      Recursive | 218.25 ms | 0.984 ms | 0.920 ms |  4.18 |    0.03 |
|                      Iterative |  52.18 ms | 0.259 ms | 0.216 ms |  1.00 |    0.00 |
|                Iterative_Array |  45.12 ms | 0.540 ms | 0.505 ms |  0.87 |    0.01 |
|            Iterative_TwoArrays |  42.23 ms | 0.161 ms | 0.142 ms |  0.81 |    0.00 |
| Iterative_TwoArrays_BitIndices |  39.37 ms | 0.122 ms | 0.114 ms |  0.75 |    0.00 |

The final code along with benchmarks can be found at https://github.com/MrKWatkins/cards-cs.