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 in Visual Basic 2005
DescriptionThis example shows how to find all ways to pick N out of M items in Visual Basic 2005.
Keywordschoose, combinatorics, combinations, VB.NET
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 (albeit in Visual Basic 6), 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)
    ' 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.
        Dim txt As String = Format$(first_allowed)
        For i As Integer = first_allowed + 1 To last_allowed
            txt = txt & " " & Format$(i)
        Next i
        solutions.Add(txt)
    Else
        ' Get solutions containing first_allowed.
        Dim partial_solutions As 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 As Integer = 1 To partial_solutions.Count
            solutions.Add(Format$(first_allowed) & _
                " " & partial_solutions(i))
        Next i

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

        ' Add these to the solutions.
        For i As Integer = 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 btnList_Click(ByVal sender As System.Object, _
    ByVal e As System.EventArgs) Handles btnList.Click
    ' Get the solutions.
    Dim solutions As New Collection()
    Dim M As Integer = Val(txtM.Text)
    Dim N As Integer = Val(txtN.Text)
    MchoseN(N, 1, M, solutions)

    ' Display the solutions.
    lstResults.Items.Clear()
    For i As Integer = 1 To solutions.Count
        lstResults.Items.Add(solutions(i))
    Next i

    txtSolutions.Text = Format$(solutions.Count)

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