Permutation listing

[Eric A. Johnson]

I'm trying to create a program to list all of the possible permutations of a
string of characters. This obviously is equal to x!, where x is the number
of characters to permutate. I have created a function to alphabetize the
string (I lowercase it before this), and another that swaps any two
characters within a string, with proper error-checking. I have fully tested
these functions to ensure they work properly. The problem lies in the fact
that the recursive procedure that I have designed, rather than iterating
through itself x! times, actually iterates 2 ^ (x - 1) times.

The code is as follows:

' Given any string, displays all permutations of the characters within the
string.

Private Sub PermutateString(ByVal originalString As String, ByVal numCalls
As Integer)

' Interesting bug: it's going through the loop 2^(x - 1) times, x = chars in
text

' Add 1 to count of iterations through the sub

Debug += 1

Dim tempString As String

Dim strLength As Integer

Dim Iterations As Integer

Dim timesToLoop As Integer

tempString = originalString

strLength = originalString.Length

Iterations = numCalls

' Go through the characters until reach the point we need to swap

For timesToLoop = 1 To Iterations - 1

' Call self to find proper swapping location

PermutateString(tempString, Iterations - timesToLoop)

Next

tempString = SwapCharsInString(tempString, strLength - Iterations + 1, _

strLength - Iterations)

txtCombinations.Text &= tempString & vbCrLf

Return

End Sub



....Any ideas, anyone? I'm kinda stuck here... and tired... heh. You don't
need to answer it for me. This is a personal project. If you can give me a
hint as to what I'm doing wrong, or how I can add to it to make it right,
that would be terrific. Thanks!

 

[Larry Lard]

I'm trying to create a program to list all of the possible permutations of a
string of characters. This obviously is equal to x!, where x is the number
of characters to permutate. I have created a function to alphabetize the
string (I lowercase it before this), and another that swaps any two
characters within a string, with proper error-checking. I have fully tested
these functions to ensure they work properly. The problem lies in the fact
that the recursive procedure that I have designed, rather than iterating
through itself x! times, actually iterates 2 ^ (x - 1) times.

I'm not going to asses whether or not your algorithm is correct; I'm
just going to point out that the erroneous behaviour suggests that
maybe you are not marking particular characters as 'used' when you use
them.

 

[Eric A. Johnson]

I think you've got it! That idea had been lurking in the back of my mind
last night... I knew that it was *something*, and part of my brain had a
vague idea it might be kinda like that, but I was so tired that the idea
never fully formed itself. I'll work on that when I get hom from work this
evening (after my final). Thanks for pointing that out!