Permutations in Visual Basic -- Generating All Possible Combinations

;
visit http://www15.brinkster.com/bubux/

Explanation and Usage

It is very useful to have all possible combinations of a string. For example: In a search engine, if the user types "mp3 rock hard," the engine should be smart enough to search for all combinations of the user input; otherwise, it will not be a powerful searching tool. These combinations would look like the following:

"mp3 rock hard"
"mp3 hard rock"
"rock mp3 hard"
"rock hard mp3"
"hard mp3 rock"
"hard rock mp3"

The Idea

I've decided to code a function that would generate all possible combinations out of a given string.

The Research

First of all, I tried searching about it in CodeGuru's forums. But all I found was that there was a function that could do that job, but in VC++. And because I know nothing of C & Cia, I didn't even look at it.

The Decision

So, what could I do? I could develop my own algorithm in Visual Basic. And that is what I've decided to do. First of all, while developing the algorithm, I asked my whole family and my neighbor (a judge) for help with the algorithm; no one could get even close. As time passed, after rewriting the whole thing from scratch for more than 20 times, I was getting closer and closer. With significant but buggy outputs, I've noticed that I would have to develop (for the 1st time in my little programmer life) a callback function. And that worked! The function generates all the 40,320 combinations of an 8-element string (in other words, "1 2 a 4 b 6 c 8") in 1.34 seconds.

The Result

' Generates all combination possibilities out of a string
Public Function PermuteString(ByVal Ztring As String, _
       Optional Base As String = "") As String

Dim TmpStrArray() As String, I As Long

' If there's only 1 element, then
If InStr(1, Ztring, " ", vbTextCompare) = 0 Then
    PermuteString = Base & " " & Ztring & vbCrLf
    Exit Function
End If

' If more than 1 element: split elements in one array of elements
TmpStrArray = Split(Ztring, " ", , vbTextCompare)


If Base = "" Then
    ' Loop trough each element and do callbacks to permute again
    For I = LBound(TmpStrArray) To UBound(TmpStrArray)
            PermuteString = PermuteString & _
            PermuteString(ReturnAllBut(TmpStrArray, I),_
                                       TmpStrArray(I))
    Next
Else
    ' Loop trough each element and do callbacks to permute again
    For I = LBound(TmpStrArray) To UBound(TmpStrArray)
            PermuteString = PermuteString & " " & _
            PermuteString(ReturnAllBut(TmpStrArray, I), _
            Base & " " & TmpStrArray(I))
    Next
End If

End Function


' Return all items in a array but 1
Public Function ReturnAllBut(ByRef Arrai() As String, _
       But As Long) _
       As String
    Dim I As Long
    For I = LBound(Arrai) To UBound(Arrai)
        If I <> But Then
           ReturnAllBut = ReturnAllBut & Arrai(I) & " "
        End If
    Next
    ReturnAllBut = RTrim(ReturnAllBut)
End Function

To Test the Speed, Use This

Public Sub TestPermutationSpeed()

Dim I As Long   ' Used in loops
Dim Nou         ' Used to calc delay
Dim NumberOfElements As Long
                ' Used to calc number of elements in PermutyString

Const NumberOfPermutations = 1
      ' Number of permutations to be done
Const PermutyString = "A B C D E F G H"
      ' String to be permuted

NumberOfElements = UBound(Split(PermutyString, " ", , _
                          vbTextCompare)) + 1
                   ' Calc number of elements in PermutyString

Nou = Timer  ' Get start time
For I = 1 To NumberOfPermutations
    ' Loop #NumberOfPermutations times
    PermuteString (PermutyString)
    ' Do permutation
Next    ' End of loop

' Display the results.
MsgBox NumberOfPermutations & " permutations of " & _
       NumberOfElements & " elements in " & _
       Timer - Nou & " seconds"
End Sub

That's all for now!



Comments

  • problem with code.

    Posted by mosu101 on 08/20/2005 06:38am

    This code works well for small numbers of phrases but when run on 11 phrases it generates an unhandled exception error (possible because its calculating 39916800 possible combinations and exhausts memory? not sure...)

    Reply
  • Keith Nieuwenhuizen

    Posted by nieukei1 on 08/05/2004 12:58am

    This generates PERMUTATIONS. i am after code which generates COMBINATIONS.

    Reply
  • This is really called permutations

    Posted by Legacy on 01/21/2004 12:00am

    Originally posted by: burken

    The right term for this is permutations, or am I wrong?
    

    Reply
  • What about without repeating combinations?

    Posted by Legacy on 12/03/2003 12:00am

    Originally posted by: MePenguin

    A bit late here, but how would you modify this to make sure no combinations, independant of order, were repeated if you picked out a subset of the elements?

    e.g.
    String="mp3 rock hard prog"

    Need all combinations of 3 words without repeating:

    mp3 rock hard
    mp3 rock prog
    mp3 hard prog
    rock hard prog

    All other combinations would be reordered repeats of these 4...

    I need this for somethign completely different, but the logic is the same - help please!

    • combination code in access vb

      Posted by nawaz on 09/03/2012 12:37pm

      hi can any one explian how to do combination in access form of 4 textbox values and diplay list of combination in onther textbox

      Reply
    • Repeating combination from long list?

      Posted by Cocotus on 09/02/2009 09:20am

      Pinky98s example works great for only 4 words in the strTotalString. But I need something for a string with like 178 words and need all combination with 3 words. Anyone knows what I have to change in the code to achieve this?

      Reply
    • RE: What about without repeating combinations?

      Posted by Pinky98 on 05/16/2005 03:16am

      The logic to do some thing like this would be completely different.
      
      All you do it loop through the string masking each alternate sub string.
      
      e.g.
      strTotalString = "mp3 rock hard prog"
      SubStrings = Split(strTotalString, " ")
      
      ReDim Combinations(UBound(SubStrings))
      For i = LBound(SubStrings) To UBound(SubStrings)
          Combinations(i) = ""
          For j = LBound(SubStrings) To UBound(SubStrings)
              If (j <> i) Then Combinations(i) = Combinations(i) & " " & SubStrings(j)
          Next j
      Next i

      Reply
    Reply
  • vb:- want some implementation

    Posted by Legacy on 01/21/2003 12:00am

    Originally posted by: pranveer

    hello sir,
    what i see in it that no one can understand what u r codeing here.Here some simplicity is required.
    Just like that how to implement this code give some simple examples that will execute diretly without increment in this file.Like to add some textbox button names,labels name . How we can know these all.

    Reply
  • EnumXXX

    Posted by Legacy on 01/20/2003 12:00am

    Originally posted by: Vitaly

    It would be best done using an enumeration function.

    Regards,
    Vitaly

    P.S. Looking for the best tooltips support? - Try http://www.tootips.net

    Reply
  • Not a callback function

    Posted by Legacy on 01/16/2003 12:00am

    Originally posted by: Scott

    I think you mean a "recursive" function :-)

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • As all sorts of data becomes available for storage, analysis and retrieval - so called 'Big Data' - there are potentially huge benefits, but equally huge challenges...
  • The agile organization needs knowledge to act on, quickly and effectively. Though many organizations are clamouring for "Big Data", not nearly as many know what to do with it...
  • Cloud-based integration solutions can be confusing. Adding to the confusion are the multiple ways IT departments can deliver such integration...

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date