What's New
Q & A
Tip Jar
C# Helper...
Follow VBHelper on Twitter
MSDN Visual Basic Community
TitleRecursively generate permutations of a collection of objects in Visual Basic 2005
DescriptionThis example shows how to recursively generate permutations of a collection of objects in Visual Basic 2005.
Keywordspermute, permutation, combinatorics, recursive, factorial, VB.NET
Function GeneratePermutations takes a parameter a collection holding the objects it should permute. It returns a collection containing other collections that contain the permutations.

The function begins by checking its parameter to see if there is only one object to permute. If there is, its only permutation consists of the object itself. The function returns a new collection containing a single collection containing the object.

If there is more than one value, the function loops through each value. GeneratePermutations removes the selected value from the values collection and recursively calls itself to generate the permutations of the remaining items. It then adds those permutations to its results with the removed item stuck in front. It restores the removed value and repeats the process, removing the next value.

Example: Consider the values ABCD. The function starts by removing the value A and recursively generating the permutations of BCD. Those are BCD, BDC, CBD, CDB, DBC, and DCB. Next the function adds the removed value A at the beginning of these to get ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.

Now the function restores the value A to the collection and removes the next value, B. It recursively generates the permutations of the remaining values ACD: ACD, ADC, CAD, CDA, DAC, DCA. It adds the removed value B to the beginning of those permutations to get BACD, BADC, BCAD, BCDA, BDAC, BCA.

The process continues until the function has generated all of the permutations of the values it was passed.

' Generate permutations of the values in the
' values collection.
' Return the result through a collection of
' collections that each hold a permutation.
Private Function GeneratePermutations(ByVal values As _
    Collection) As Collection
    Dim results As New Collection

    ' See if there is only one value.
    If values.Count = 1 Then
        ' Return a collection containing one
        ' permutation equal to the single value.
        results.Add(New Collection)
        Return results
    End If

    ' Build permutations starting with
    ' each possible first item.
    results = New Collection
    Dim num_values As Integer = values.Count
    For i As Integer = 1 To num_values
        ' Save this value.
        Dim first_value As Object = values.Item(i)

        ' Remove the item.

        ' Generate the permutations of the
        ' remaining values.
        Dim new_permutations As Collection = _

        ' Make permutations by adding first_value
        ' to the beginning of each of the new
        ' permutations.
        For j As Integer = 1 To new_permutations.Count
            ' Add the first item.
            Dim new_result As New Collection

            ' Add the rest of the items in the jth
            ' new permutation.
            For k As Integer = 1 To _
            Next k

            ' Add this new permutation to the results.
        Next j

        ' Restore the removed value.
        If i > values.Count Then
            values.Add(first_value, , i)
        End If
    Next i

    ' Return the results.
    Return results
End Function
For information on other algorithms (albeit in Visual Basic 6), see my book Ready-to-Run Visual Algorithms.
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.