-
Mar 21st, 2015, 02:17 PM
#1
Thread Starter
Hyperactive Member
[RESOLVED] Permutation
Hi all,
I am looking for a recursive algorithm that could display all possible permutations of 4 characters with themselves. Let's say we have the following string "a, b, c, d". We know from math that all these possible permutations should be n!/(n-k)! which in this case is 24. So I want to display all these cases: "a, b, d, c", "a, c, b, d", "a, d, b, c", "a, c, d, b" ..... and so on. Is it possible to make a generalisation ? Thank you.
-
Mar 21st, 2015, 03:01 PM
#2
Re: Permutation
Well it could easily be done with 4 nested loops
-
Mar 21st, 2015, 03:05 PM
#3
Re: Permutation
Of course using 4 nested loops would assume that you just have 4 values, if that number of values could be variable then recursion would probably be in order
-
Mar 21st, 2015, 03:55 PM
#4
Re: Permutation
Just out of curiosity and a little off topic I 'm wondering why /(n-k)! when n! = 24 when n = 4
Anything I post is an example only and is not intended to be the only solution, the total solution nor the final solution to your request nor do I claim that it is. If you find it useful then it is entirely up to you to make whatever changes necessary you feel are adequate for your purposes.
-
Mar 21st, 2015, 04:11 PM
#5
Re: Permutation
A very quick search on Permutation turn this code snippet up.
Code:
Option Explicit
Private mColPermutations As Collection
Private Sub Command1_Click()
Dim lPerCount As Long, lPermStr As String
Dim i As Long
lPermStr = "abcd"
Set mColPermutations = New Collection
lPerCount = GetPermutation(lPermStr) '(Recursive Function)
'Show them..
List1.Clear
For i = 1 To mColPermutations.Count
List1.AddItem mColPermutations(i)
Next
Set mColPermutations = Nothing
End Sub
Private Function GetPermutation(Y As String, Optional X As String = vbNullString) As Long
Dim idx As Long, pos As Long
Static cnt As Long
If Len(X) = 0 Then cnt = 0
pos = Len(Y)
If pos < 2 Then
mColPermutations.Add X & Y
cnt = cnt + 1
Else
For idx = 1 To pos
GetPermutation Left$(Y, idx - 1) & Right$(Y, pos - idx), X & Mid$(Y, idx, 1)
Next
End If
GetPermutation = cnt
End Function
-
Mar 21st, 2015, 05:14 PM
#6
Thread Starter
Hyperactive Member
Re: Permutation
Originally Posted by DataMiser
Well it could easily be done with 4 nested loops
So if the string has 100 characters we should use 100 nested loops ... What will we do when the string length is in run-time determined ?
Originally Posted by jmsrickland
Just out of curiosity and a little off topic I 'm wondering why /(n-k)! when n! = 24 when n = 4
Well, in this case n is the total number of characters in the string while k is the size of a subgroup of that string we are interested in. Consequently, 4! (wich is 24) is divided by (4-4)!, that means 24/1. Thus, if we were interested to find, let's say, all 2 characters subgroups we should have following 12 possibilities : ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db and dc. As we know, it's no big deal but a common algebraic formula at the high school level.
-
Mar 21st, 2015, 05:29 PM
#7
Re: Permutation
we just had that topic over here: http://www.vbforums.com/showthread.p...ts-Suggestions
the recursive .net function looks like this:
Code:
Private Sub AddCombos1(ByVal Solutions As List(Of String), ByVal Solution As String, ByVal PossibleChars As String, Optional MinStrLen As Integer = 1)
If Solution.Length >= MinStrLen Then
Solutions.Add(Solution)
End If
For i As Int32 = 0 To PossibleChars.Length - 1
AddCombos1(Solutions, Solution & PossibleChars(i), PossibleChars.Remove(i, 1), MinStrLen)
Next
End Sub
it should not be hard to translate to vb6. replace list (of string) with a collection.
the code does also gice you 'a' 'b' etc, i.e. combinations where not all letters are used.
-
Mar 21st, 2015, 06:17 PM
#8
Re: Permutation
Originally Posted by Daniel Duta
So if the string has 100 characters we should use 100 nested loops ... What will we do when the string length is in run-time determined ?
Then as I said in my second post recursion comes into play
-
Mar 21st, 2015, 06:32 PM
#9
Thread Starter
Hyperactive Member
Re: Permutation
Hi Mark,
Your function is very ingenious and works fine. In addition, the results are pure permutations in terms of recursivity. If we take a string like "aaaa" the function will return 24 cases as well. And this is correct. I just wonder why the number of iterations within your GetPermutation function is always greater than total number of subgroups. For example, for 3 characters we have 6 combinations and your function is called 10 times, for 4 characters we have 24 combinations and the function is called 41 times...
Originally Posted by digitalShaman
I am sorry digitalShaman but I don't know how to convert the procedure above in VB6. It doesn't seem too complex but I am not sure if it is in a way or other over the Mark's solution. The ideea is to get results in terms of mathematical permutations. Thank you both.
-
Mar 21st, 2015, 06:59 PM
#10
Re: Permutation
If you place
Debug.Print Y & " " & X
At the top of the recursive function you will see the parameters that are being passed to the call. It is just a matter of how it is looping and building the parameters to make the next call.
-
Mar 22nd, 2015, 03:25 AM
#11
Re: [RESOLVED] Permutation
I am sorry digitalShaman but I don't know how to convert the procedure above in VB6. It doesn't seem too complex but I am not sure if it is in a way or other over the Mark's solution. The ideea is to get results in terms of mathematical permutations. Thank you both.
this is the translation with an example call:
Code:
Public Sub test()
Dim col As New Collection
AddCombos col, "", "abcd", 4
Dim s As Variant
For Each s In col
Debug.Print s
Next
End Sub
Private Sub AddCombos(ByRef Solutions As Collection, ByVal Solution As String, ByVal PossibleChars As String, Optional MinStrLen As Integer = 1)
Dim i As Integer
Dim sRemaining As String
If Len(Solution) >= MinStrLen Then
Solutions.Add Solution
End If
For i = 1 To Len(PossibleChars)
sRemaining = Mid(PossibleChars, 1, i - 1) & Mid(PossibleChars, i + 1)
AddCombos Solutions, Solution & Mid(PossibleChars, i, 1), sRemaining, MinStrLen
Next
End Sub
its almost the same as mark's
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|