Results 1 to 11 of 11

Thread: [RESOLVED] Permutation

  1. #1

    Thread Starter
    Hyperactive Member Daniel Duta's Avatar
    Join Date
    Feb 2011
    Location
    Bucharest, Romania
    Posts
    396

    Resolved [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.

  2. #2
    PowerPoster
    Join Date
    Feb 2012
    Location
    West Virginia
    Posts
    14,205

    Re: Permutation

    Well it could easily be done with 4 nested loops

  3. #3
    PowerPoster
    Join Date
    Feb 2012
    Location
    West Virginia
    Posts
    14,205

    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

  4. #4
    PowerPoster
    Join Date
    Jan 2008
    Posts
    11,074

    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.

  5. #5
    PowerPoster
    Join Date
    Jun 2001
    Location
    Trafalgar, IN
    Posts
    4,141

    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

  6. #6

    Thread Starter
    Hyperactive Member Daniel Duta's Avatar
    Join Date
    Feb 2011
    Location
    Bucharest, Romania
    Posts
    396

    Re: Permutation

    Quote Originally Posted by DataMiser View Post
    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 ?
    Quote Originally Posted by jmsrickland View Post
    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.

  7. #7
    Frenzied Member
    Join Date
    May 2014
    Location
    Central Europe
    Posts
    1,372

    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.

  8. #8
    PowerPoster
    Join Date
    Feb 2012
    Location
    West Virginia
    Posts
    14,205

    Re: Permutation

    Quote Originally Posted by Daniel Duta View Post
    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

  9. #9

    Thread Starter
    Hyperactive Member Daniel Duta's Avatar
    Join Date
    Feb 2011
    Location
    Bucharest, Romania
    Posts
    396

    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...
    Quote Originally Posted by digitalShaman View Post
    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.

  10. #10
    PowerPoster
    Join Date
    Jun 2001
    Location
    Trafalgar, IN
    Posts
    4,141

    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.

  11. #11
    Frenzied Member
    Join Date
    May 2014
    Location
    Central Europe
    Posts
    1,372

    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
  •  



Click Here to Expand Forum to Full Width