Combination / Permutation

[Bert Johnson]

How could I go about finding every different permutation of a string possible? Like, I want to be able to go through each possibility of a scrambled string:

Example:
abc goes to
abc, acb, bac, bca, cab, cba

All help is appreciated! Thanks!

[netSurfer]

According to the Statistician at my company, you need the factorial number of the letter count:

abc = 3 (how many letters)

3 X 2 X 1= 6

if doing abcd = 4

4 X 3 X 2 X 1 = 24

So if you wanna do this in code, get the length of your string and then just subtract 1 until you get to 1.

This works if there is not repeated letters

no aab or acc etc.


------------------
'cos Buzby says so!'

[Bert Johnson]

How exactly does that help me get the actual strings? I don't follow.

[netSurfer]

Ok, I misunderstood a bit. I thought you wanted the number of possible combinations. You would need that number any way. It's an interesting problem, the places where I've needed to do it, I've done it manually (YUCK!). Let me think on it for a bit. I'm at work right now but I will think about it. My first thought would be to dump the seperate pieces of string into an array (take a,b,c and - array(0)= a, array(1) = b ... or array(a,b,c)) and figure the permutations. I will see what I can come up with. If you figure it out, can you let me know? I know that there are programs to do this (I've seen them in Linux) but I'm not entirely sure how to do it.

------------------
'cos Buzby says so!'

[netSurfer]

I've talked to some statatician friends of mine and their not sure how to do it via code. I'm sure there is an easy way to do it but I haven't figured it out yet. I'll see if I can find something on the net about it over the weekend. Let me know if you figure it out ok? I'm curious about this. Thanks


------------------
'cos Buzby says so!'

[Guv]

I wrote a Mainframe program to do this many years ago. I do not remember the precise algorithm, but will try to give you the general idea.

First a warning: Are you aware of how fast factorials grow?
10 factorial is 3,628,808
15 factorial is 1.3E12
20 factorial is 2.4E18

The algorithm I used came from an article in Scientific American about 10-15 years ago. If you know of a way to search back issues, you might find it (I think an index to SA exists). I think it was in the mathematical games section.

The basic approach was to start with a string of letters and make simple exchanges.
The scheme was something like the following.

ABCDEF BACDEF BCADEF BCDAEF BCDEAF BCDEFA
CBDEFA CBDEAF CBDAEF CBADEF CABDEF ACBDEF
ACBDFE CABDFE CBADFE CBDAFE CBDFAE BCDFEA

Note that "A" moves back and forth. When it is at either end of string, exchange the two letters at the other end, and reverse direction.

Not 100% sure this is correct algorithm. I know that a single letter moves as shown above, but perhaps another letter is moved, after the first has moved to the end of the string.

I do not remember how to determine when all permutations have been generated. You could count thm, but I think I used a recursive program which had had some other way to know when it was done.

The algorithm was alleged to be the fastest possible due to being able to use "Half Exchanges" (Keep the moving element in a temporary place, overwrite it in string, and copy from temporary to its next place in string). I believe that other algorithms do "full exchanges" or worse to generate the next string.


------------------

This problem has been eating at me since the first post I read.

Now thanks to Guv pointing me in the right direction, I think I have it. I did not have patience to test more than five characters. Here goes:

Option Explicit

Private Sub Command1_Click()
Dim maxcount As Integer
Dim w As Integer
Dim x As Integer
Dim y As Integer
Dim z As Integer
Dim holder As Integer
Dim temp As String
maxcount = 1
For x = Len(Text1.Text) To 1 Step -1
   maxcount = maxcount * x
Next x

ReDim myarray(1 To maxcount) As String
ReDim chararray(1 To Len(Text1.Text)) As String

For x = 1 To Len(Text1.Text)
   chararray(x) = Mid(Text1.Text, x, 1)
Next x
holder = 0
For w = 2 To (Len(Text1.Text) - 1)
   For x = 1 To Len(Text1.Text)
      For z = 1 To (Len(Text1.Text) - 1)
         holder = holder + 1
         For y = 1 To Len(Text1.Text)
            myarray(holder) = myarray(holder) & chararray(y)
         Next y
         temp = chararray(z)
         chararray(z) = chararray(z + 1)
         chararray(z + 1) = temp
      Next z
   Next x
   If w <= Len(Text1.Text) Then
      temp = chararray(w)
      chararray(w) = chararray(w + 1)
      chararray(w + 1) = temp
   End If
Next w
For x = 1 To holder
   MsgBox myarray(x)
Next x
End Sub

------------------
Boothman

There is a war out there, and it is about who controls the information, it's all about the information.

Does not work with more than 5 characters. Will continue working on it.

------------------
Boothman

There is a war out there, and it is about who controls the information, it's all about the information.

[This message has been edited by Boothman_7 (edited 02-11-2000).]