Home Search   What's New Index Books Links Q & A Newsletter Banners   Feedback Tip Jar MSDN Visual Basic Community

Title Find all ways to pick N out of M items in Visual Basic 2005 This example shows how to find all ways to pick N out of M items in Visual Basic 2005. choose, combinatorics, combinations, VB.NET Algorithms

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
Else
' Get solutions containing first_allowed.
Dim partial_solutions As New Collection()
If N = 1 Then
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
" " & 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
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