1
\$\begingroup\$

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:

n! / (r! * (n-r)!)

This is implemented in code as:

(r+1) \ 1 * (r+2) \ 2 * (r+3) \ 3 ... n \ (n-r)

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

(n+r-1)! / (r! * (n-1)!)

This is implemented in code as:

(r+1) \ 1 * (r+2) \ 2 * (r+3) \ 3 ... (n+r-1) \ (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 “\” 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}.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.