Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
 
MSDN Visual Basic Community
 
 
 
 
TitleFind all ways to pick N out of M items
Keywordschoose, combinatorics, combinations
CategoriesAlgorithms
 
This program uses a recursive subroutine that first checks combinations containing the first allowed value, and then considers combinations that do not contain the first allowed value.

This is a modified tree search. It looks in all possible combinations of items to find those that have exactly N items selected.

For more information on tree searching and other algorithms, see my book Ready-to-Run Visual Basic Algorithms, Second Edition.

 
' Pick N items from a list between first_allowed
' and last_allowed. Return the solutions in the
' collection as space-separated characters.
'
' For example, MchoseN(3, 2, 5, solutions) means
' pick 3 items from the values 2, 3, 4, 5 and
' returns 2 3 4, 2 3 5, and 3 4 5.
Private Sub MchoseN(ByVal N As Integer, ByVal first_allowed _
    As Integer, ByVal last_allowed As Integer, ByVal _
    solutions As Collection)
Dim i As Integer
Dim txt As String
Dim partial_solutions As Collection

    ' If N < 1, we don't need to pick any more
    ' items.
    ' If N > last_allowed - first_allowed + 1,
    ' there are too few items for a solution.
    ' If N = last_allowed - first_allowed + 1,
    ' all the items must be in the solution.

    If N < 1 Then
        ' We don't need to pick any more.
        ' Do nothing.
    ElseIf N > last_allowed - first_allowed + 1 Then
        ' There are not enough items.
        ' Do nothing.
    ElseIf N = last_allowed - first_allowed + 1 Then
        ' All the items must be in the solution.
        txt = Format$(first_allowed)
        For i = first_allowed + 1 To last_allowed
            txt = txt & " " & Format$(i)
        Next i
        solutions.Add txt
    Else
        ' Get solutions containing first_allowed.
        Set partial_solutions = New Collection
        If N = 1 Then
            partial_solutions.Add ""
        Else
            MchoseN N - 1, first_allowed + 1, last_allowed, _
                partial_solutions
        End If

        ' Add first_allowed to make the full
        ' solutions.
        For i = 1 To partial_solutions.Count
            solutions.Add Format$(first_allowed) & _
                " " & partial_solutions(i)
        Next i

        ' Get solutions not containing first_allowed.
        Set partial_solutions = New Collection
        MchoseN N, first_allowed + 1, last_allowed, _
            partial_solutions

        ' Add these to the solutions.
        For i = 1 To partial_solutions.Count
            solutions.Add partial_solutions(i)
        Next i
    End If
End Sub
 
As partial verification, the program also calculates the number of combinations directly using the formula:

    # combinations = M! / N! / (M - N)!
 
Private Sub Command1_Click()
Dim M As Integer
Dim N As Integer
Dim solutions As Collection
Dim i As Integer
Dim txt As String

    ' Get the solutions.
    Set solutions = New Collection
    M = CInt(txtM.Text)
    N = CInt(txtN.Text)
    MchoseN N, 1, M, solutions

    ' Display the solutions.
    For i = 1 To solutions.Count
        txt = txt & solutions(i) & vbCrLf
    Next i

    txtResult.Text = txt
    lblSolutions.Caption = Format$(solutions.Count)

    ' Calculate the number of combinations directly.
    lblCalculatedNumber.Caption = _
        Factorial(M) / _
        Factorial(N) / _
        Factorial(M - N)
End Sub
 
 
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated