Iterating over combinations

Question

Background

The following describes the real world problem that my code is intended to solve. It is may help you understand what the code is doing and why. I don't think this is strictly necessary in order to review the code, so feel free to skip to the section headed "Problem"

I have an application that creates a season schedule for a sports league. There are two places where it needs to process all possible combinations of a given number of objects selected from a larger set of objects.

1. If there are L clubs in the league and T clubs attend each tournament (T < L), process all possible tournaments. This requires selecting all combinations of T objects selected from a set of L objects without repetition (a club is either at a tournament or not, it can't be there twice).
2. If there are S rounds in the season and C possible ways a round can be configured, process all possible seasons. This requires selecting all combinations of S objects selected from a set of C objects with repetition allowed (there can be more than one round with the same configuration in a season).

In both cases I can create a List of the objects to be selected from, so now I only have to deal with the index numbers of the objects in the List (instead of the objects themselves). I intend to process all the possible combinations, so I need a way to iterate over the set of combinations.

Problem

Create a class that implements IEnumerable(Of Integer) that will return all possible combinations of r integers selected from the first n non-negative integers, with the option to allow or disallow repetition. I also want to provide a property that calculates the number of possible combinations.

Code

''' <summary>Represents a set of possible combinations of integers</summary>
<System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")>
Public Class Combinations
    Implements IReadOnlyCollection(Of Integer())

    Private ReadOnly choose, total As Integer, repetition As Boolean

    ''' <summary>Create a new Combinations object</summary>
    ''' <param name="pick">Number of items to be picked</param>
    ''' <param name="pickfrom">Number of items to pick from</param>
    ''' <param name="allowRepetition">True if items may be picked more than once</param>
    ''' <remarks>'pick' is allowed to be zero, in which case zero combinations will returned</remarks>
    Sub New(pick As Integer, pickFrom As Integer, allowRepetition As Boolean)
        If pick < 0 Then Throw New ArgumentException(
            "Number of items to pick must be a non-negative integer", "pick")
        If pickFrom <= 0 Then Throw New ArgumentException(
            "Number of items to pick from must be a positive integer", "pickFrom")
        If Not allowRepetition And pick > pickFrom Then Throw New ArgumentException(
            "Number of items to pick must not exceed the number of items to pick from", "pick")

        repetition = allowRepetition
        choose = pick
        total = pickFrom
    End Sub

    ''' <summary>Returns the number of possible values</summary>
    ''' <exception cref="OverflowException">The number of possible values exceeds Integer.MaxValue</exception>
    Public ReadOnly Property Count As Integer Implements IReadOnlyCollection(Of Integer()).Count
        Get
            Return CInt(LongCount)
        End Get
    End Property

    ''' <summary>Returns the number of possible values</summary>
    ''' <exception cref="OverflowException">The number of possible values exceeds or approaches Long.MaxValue</exception>
    ''' <remarks>This replaces the LongCount extension method of IEnumerable which iterates through the entire collection</remarks>
    <System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1720:IdentifiersShouldNotContainTypeNames", MessageId:="long")>
    Public ReadOnly Property LongCount As Long
        Get
            If choose < 1 Then Return 0 'If choosing 0 combinations, count must be 0 rather than 1

            Dim minNumer As Long = If(repetition, total - 1, If(choose < total - choose, total - choose, choose))
            Dim maxDenom As Long = If(repetition, choose, If(choose < total - choose, choose, total - choose))
            Dim result As Long = 1

            For iter As Long = 1 To maxDenom
                result *= minNumer + iter
                result \= iter
            Next
            Return result
        End Get
    End Property

    ''' <summary>Gets the enumerator that can be used to select each possible value</summary>
    Public Iterator Function GetEnumerator() As IEnumerator(Of Integer()) Implements IEnumerable(Of Integer()).GetEnumerator
        If choose < 1 Then Exit Function 'If choosing 0 combinations, exit without yielding a value

        Dim value(choose - 1) As Integer
        If Not repetition Then value = Enumerable.Range(0, choose).ToArray
        Dim index As Integer = choose - 1

        Do
            Yield value
            'Exit if iteration is complete
            If value(0) = total - If(repetition, 1, choose) Then Exit Do

            'Find the rightmost element that can be incremented and increment it
            Dim oldIndex As Integer = index
            Do While value(index) = total - If(repetition, 1, choose - index)
                index -= 1
            Loop
            value(index) += 1

            'If index changed, reset all elements to the right of the new index
            If index <> oldIndex Then
                Do
                    index += 1
                    value(index) = value(index - 1) + If(repetition, 0, 1)
                Loop Until index = choose - 1
            End If
        Loop
    End Function

    ''' <summary>Non-generic method required for compatibility</summary>
    Private Function GetEnumerator1() As IEnumerator Implements IEnumerable.GetEnumerator
        Return GetEnumerator()
    End Function
End Class

Request for review

I welcome any suggestions for improving speed of processing or readability of the code, as well as any edge cases I have missed or user interfaces that could be improved. There are also some specific areas where I am not sure I have made the right decision and would certainly appreciate your comments on them:

1. The class implements IReadOnlyCollection(Of Integer) rather than IEnumerable(Of Integer) as the former provides a Count property. The latter has a Count extension method that iterates over the collection to count the items (and so can be slow for large collections), I believe that by implementing IReadOnlyCollection(Of Integer), I am signalling to the user that my Count property is reasonably efficient.

2. The number of possible combinations can quickly become very large, so in addition to a Count property that returns an Integer, I provide a LongCount property that returns a Long. In both cases, I allow an OverflowException to be thrown if the number of combinations is too high. I believe that I have ensured that I have avoided any OverflowException in other cases by alternating the multiplication and division operations during the calculations.

3. I chose to allow the user to specify that zero numbers should be selected (and in that case, the iterator function exits without yielding anything. In my application, the number of items to be picked is calculated and could be zero; treating this as a collection of zero objects works for me, but I'm not sure whether or not that would seem reasonable to another user.

4. I am forced to implement the non-generic IEnumerable.GetEnumerator function and have done so with the GetEnumerator1 function. This looks odd to me, is there a better way of satisfying the requirements of the interface?

Methodology

The code for the LongCount and GetEnumerator methods may seem a little obscure. Here is some information about the methodology

LongCount
The formula for the number of combinations of r items chosen without repetition from a set of n items is:

$$\frac{n!}{r! (n-r)!}$$

This is implemented in code as:

$$(r+1) \backslash 1 \times (r+2) \backslash 2 \times (r+3) \backslash 3 \times \cdots \times n \backslash (n-r)$$

The formula for the number of combinations of r items chosen with repetition from a set of n items is:

$$\frac{(n+r-1)!}{r! (n-1)!}$$

This is implemented in code as:

$$(r+1) \backslash 1 \times (r+2) \backslash 2 \times (r+3) \backslash 3 \times \cdots \times (n+r-1) \backslash (n-1)$$

The interesting thing about these sequences is that there is never a remainder in any of the division operations, so I can use integer division (the “\$\backslash\$” operator) without losing precision.

GetEnumerator
The current selection will be stored in an array of integers called value. The integers in value will always be in ascending order. If repetition is allowed, the array is initially all zeros, otherwise it is initialised to the first choose non-negative numbers. An integer called index contains the index of the element of the value array that is currently being incremented; its initial value is choose - 1, the last index of the array.

The main part of the method is an infinite loop that Yields the current value each time round the loop. The rest of the logic is difficult to describe; I'll do so with a simple example where we are picking 3 items from a set of 5.

• If repetition is allowed, value will initially be {0, 0, 0} and index will be 2. The element at index 2 is incremented each time round the loop until it is the highest it can be and value is {0, 0, 4}. Now index is decremented to 1 and we increment the element at index 1 until it is the highest it can be and value is {0, 4, 4}. Finally index is decremented to 0 and we increment the element at index 0 until it is the highest it can be and value is {4, 4, 4}.

• If repetition is not allowed, value will initially be {0, 1, 2} and index will be 2. The element at index 2 is incremented each time round the loop until it is the highest it can be and value is {0, 1, 4}. Now the 2nd element is incremented and the values after that element are reset to the lowest they can be making value {0, 2, 3}. The loop continues incrementing the 3rd element until value is {0, 2, 4}. The 2nd element is incremented again yielding {0, 3, 4}. The 1st element is incremented and the last two elements are set to the lowest they can be yielding {1, 2, 3}. The whole process is repeated yielding {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}.

Answer 1

    Public ReadOnly Property Count As Integer Implements IReadOnlyCollection(Of Integer()).Count
        Get
            Return CInt(LongCount)

Should this be

            Return If(LongCount > Integer.MaxValue, Integer.MaxValue, CInt(LongCount))

? MSDN doesn't seem to be explicit on what Count should return if the collection has more than MaxValue elements, but I can see some advantage to giving the nearest possible answer rather than the lowest bits.

---

    Public ReadOnly Property LongCount As Long

It seems to me that if the number of elements could be so big that you need a LongCount then IEnumerable is not the right interface to implement. At the very least, you need some way to randomly sample elements because you can't count on being able to iterate through all of them in your lifetime.

---

            If choose < 1 Then Return 0 'If choosing 0 combinations, count must be 0 rather than 1

This may be appropriate for your use case, but it's non-standard. For general purpose use I would expect it to return the empty set, once.

---

            Dim minNumer As Long = If(repetition, total - 1, If(choose < total - choose, total - choose, choose))
            Dim maxDenom As Long = If(repetition, choose, If(choose < total - choose, choose, total - choose))

The nested Ifs are a bit hard to follow, but I think that this has an optimisation which only applies when Not repetition. IMO it would be worth pulling out a static method which just calculates the binomial coefficient, employing the optimisation, and then this method would be reduced to little more than

              return Binomial(If(repetition, total+choose-1, total), choose)

Also, I think you can use one fewer auxiliary variable if you reorder the calculation as

$$n \backslash 1 \times (n-1) \backslash 2 \times (n-2) \backslash 3 \times \cdots \times (n-r+1) \backslash r$$

---

GetEnumerator() looks fairly clean - I'm a C# user rather than a VB.Net user, and I find it ugly, but I think that's almost entirely VB syntax rather than your code. There is one thing which it would be nice to tidy up if possible:

        Dim value(choose - 1) As Integer
        If Not repetition Then value = Enumerable.Range(0, choose).ToArray

I assume that the Dim assigns an array which is then thrown straight in the garbage If Not repetition. If so, can that be avoided?

---

To your specific questions:

1. The class implements IReadOnlyCollection(Of Integer) rather than IEnumerable(Of Integer) as the former provides a Count property. The latter has a Count extension method that iterates over the collection to count the items (and so can be slow for large collections), I believe that by implementing IReadOnlyCollection(Of Integer), I am signalling to the user that my Count property is reasonably efficient.

Yes. Unfortunately, the Enumerable.Count extension method only has a special case for ICollection(Of T), and not for IReadOnlyCollection(Of T).

An idea for further extension would be to implement IReadOnlyList(Of Integer()) and allow direct indexing. That would be a big step towards what I commented earlier about random selection.

2. The number of possible combinations can quickly become very large, so in addition to a Count property that returns an Integer, I provide a LongCount property that returns a Long. In both cases, I allow an OverflowException to be thrown if the number of combinations is too high. I believe that I have ensured that I have avoided any OverflowException in other cases by alternating the multiplication and division operations during the calculations.

Perhaps instead of returning a Long it should return a System.Numerics.BigInteger?

3. I chose to allow the user to specify that zero numbers should be selected (and in that case, the iterator function exits without yielding anything. In my application, the number of items to be picked is calculated and could be zero; treating this as a collection of zero objects works for me, but I'm not sure whether or not that would seem reasonable to another user.

As noted above, this is not the standard combinatorial interpretation of selecting 0 objects.

4. I am forced to implement the non-generic IEnumerable.GetEnumerator function and have done so with the GetEnumerator1 function. This looks odd to me, is there a better way of satisfying the requirements of the interface?

I don't know enough about VB syntax to give a definite answer, but I suspect that there isn't a better way.