Permutations?

[ChrisL]

I really have not got a clue where to start with this.

Lets say you have 6 numbers or characrters in an array some numbers or characters can be duplicated

$aArray[1] = "A"

$aArray[2] = "A"

$aArray[3] = "1"

$aArray[4] = "3"

$aArray[5] = "9"

$aArray[6] = "1"

How would you work through this to check all permutations?

Thanks

[nfwu]

For $a = 1 to 6
For $b = 1 to 6
For $c = 1 to 6
For $d = 1 to 6
For $e = 1 to 6
For $f = 1 to 6
     ConsoleWrite($aArray[$a]&$aArray[$b]&$aArray[$c]&$aArray[$d]&$aArray[$e]&$aArray[$f])
Next
Next
Next
Next
Next
Next

#)

[ChrisL]

For $a = 1 to 6
For $b = 1 to 6
For $c = 1 to 6
For $d = 1 to 6
For $e = 1 to 6
For $f = 1 to 6
     ConsoleWrite($aArray[$a]&$aArray[$b]&$aArray[$c]&$aArray[$d]&$aArray[$e]&$aArray[$f])
Next
Next
Next
Next
Next
Next

#)

Thanks but...

I should have said you can only use each entry once in the string unfortunately with this you could get a return string of AAAAAA

[SmOke_N]

Someone was working on a better version, but this is the one I use when I need to do a permutation (written by dev\null)

expandcollapse popup

$permutarray = permute("1234")
$msg = ""
For $n = 1 To $permutarray[0]
    $msg = $msg & $permutarray[$n] & @CRLF
Next
MsgBox(0,"", $msg)

Func rotate($sString, $nRotateLevel)
    Local $aStringArray = StringSplit($sString,"")
    Local $nStartRotate = $aStringArray[0] - $nRotateLevel + 1
    Local $n, $tempchar, $tempstr = "", $retval = ""
    For $n = 1 To $nStartRotate - 1
        $tempstr= $tempstr & $aStringArray[$n]
    Next
    $tempchar = $aStringArray[$nStartRotate]
    For $n = $nStartRotate+1 To $aStringArray[0]
        $retval = $retval & $aStringArray[$n]
    Next
    $retval = $tempstr & $retval & $tempchar
    Return $retval
EndFunc   ;==>rotate

Func permute_internal($sString, $nRotateLevel, ByRef $permutations)
    Local $n, $str
    Dim $arr[$nRotateLevel]
    If $nRotateLevel = 2 Then
        $permutations = $permutations & ":" & rotate($sString,$nRotateLevel)
        Return
    EndIf
    $str = $sString
    For $n = 0 To $nRotateLevel -1
        $str = rotate($str,$nRotateLevel)
        $arr[$n] = $str
        ;--- special check, to stop a level beeing printed twice ---
        If not (($n = 0) AND (StringLen($sString) > $nRotateLevel)) Then
            $permutations = $permutations & ":" & $arr[$n]
        EndIf
        permute_internal($arr[$n],$nRotateLevel-1,$permutations)
    Next
EndFunc   ;==>permute_internal

Func permute($sString)
    Global $permutations = ""
    permute_internal($sString,StringLen($sString),$permutations)
    $permutations = StringTrimLeft($permutations,1)
    Return StringSplit($permutations,":")
EndFunc   ;==>permute

[ChrisL]

Cheers Ron

[litlmike]

Someone was working on a better version, but this is the one I use when I need to do a permutation (written by dev\null)

expandcollapse popup

$permutarray = permute("1234")
$msg = ""
For $n = 1 To $permutarray[0]
    $msg = $msg & $permutarray[$n] & @CRLF
Next
MsgBox(0,"", $msg)

Func rotate($sString, $nRotateLevel)
    Local $aStringArray = StringSplit($sString,"")
    Local $nStartRotate = $aStringArray[0] - $nRotateLevel + 1
    Local $n, $tempchar, $tempstr = "", $retval = ""
    For $n = 1 To $nStartRotate - 1
        $tempstr= $tempstr & $aStringArray[$n]
    Next
    $tempchar = $aStringArray[$nStartRotate]
    For $n = $nStartRotate+1 To $aStringArray[0]
        $retval = $retval & $aStringArray[$n]
    Next
    $retval = $tempstr & $retval & $tempchar
    Return $retval
EndFunc   ;==>rotate

Func permute_internal($sString, $nRotateLevel, ByRef $permutations)
    Local $n, $str
    Dim $arr[$nRotateLevel]
    If $nRotateLevel = 2 Then
        $permutations = $permutations & ":" & rotate($sString,$nRotateLevel)
        Return
    EndIf
    $str = $sString
    For $n = 0 To $nRotateLevel -1
        $str = rotate($str,$nRotateLevel)
        $arr[$n] = $str
        ;--- special check, to stop a level beeing printed twice ---
        If not (($n = 0) AND (StringLen($sString) > $nRotateLevel)) Then
            $permutations = $permutations & ":" & $arr[$n]
        EndIf
        permute_internal($arr[$n],$nRotateLevel-1,$permutations)
    Next
EndFunc   ;==>permute_internal

Func permute($sString)
    Global $permutations = ""
    permute_internal($sString,StringLen($sString),$permutations)
    $permutations = StringTrimLeft($permutations,1)
    Return StringSplit($permutations,":")
EndFunc   ;==>permute

Is there a version of this script that does not StringSplit the Strings into individual characters? Meaning, what if I wanted to permutate "california", "nevada", "chicago"? With each of those representing one element of the permutations (so 3 elements total) and not 23 elements, which is the amount of letters in those three words?. Is there a version of this already completed somewhere on the forums, I have been able to locate one.

[SmOke_N]

Is there a version of this script that does not StringSplit the Strings into individual characters? Meaning, what if I wanted to permutate "california", "nevada", "chicago"? With each of those representing one element of the permutations (so 3 elements total) and not 23 elements, which is the amount of letters in those three words?. Is there a version of this already completed somewhere on the forums, I have been able to locate one.

No.

Edit:

In addition to the no, based on your question, I'm almost left to believe you don't know exactly what a permutation is... That or I have no idea what you're really trying to do.

Edited May 3, 2008 by SmOke_N

[danielkza]

No.

Edit:

In addition to the no, based on your question, I'm almost left to believe you don't know exactly what a permutation is... That or I have no idea what you're really trying to do.

I think he wants to do:

california|chicago|nevada

nevada|california|chicago

chigado|nevada|california

etc...

[SmOke_N]

loop 1 to 3

[1]|[2]|[3]

[1]|[3]|[2]

[2]|[1]|[3]

[2]|[3]|[1]

[3]|[1]|[2]

[3]|[2]|[1]

Edit:

Don't really need the loop but without a real life situation, what is asked is nothing more than the above.

Edited May 3, 2008 by SmOke_N

[litlmike]

I think he wants to do:

california|chicago|nevada

nevada|california|chicago

chigado|nevada|california

etc...

loop 1 to 3

[1]|[2]|[3]

[1]|[3]|[2]

[2]|[1]|[3]

[2]|[3]|[1]

[3]|[1]|[2]

[3]|[2]|[1]

Edit:

Don't really need the loop but without a real life situation, what is asked is nothing more than the above.

Sorry, maybe I am confusing 'permutation' and 'combination' (or maybe even some other name I don't know). What I am looking for in more details, to use Smoke's number example:

[1]

[1]|[2]

[1]|[2]|[3]

[1]|[3]

[1]|[3]|[2]

[2]

[2]|[1]

[2]|[1]|[3]

[2]|[3]

[2]|[3]|[1]

[3]

[3]|[1]

[3]|[1]|[2]

[3]|[2]

[3]|[2]|[1]

However, I would want the number of elements to be variable. So the user might input: california|chicago|nevada , or the user might input california|chicago|nevada|arizona|colorado|and so on...

TIA

[MikeP]

What you wanna do is this :

- Ask the user to fill your array

- Check the size of that array

- For $setSize = 1 To $arraySize Do $resultArray[$setSize] = extractAllPossibleSets($array, $setSize)

- Parse $resultArray

- Sort $resultArray alphabetically

extractAllPossibleSets would return an array of valid sets for a given set size

Parsing the resultArray would turn this :

[ [ 0,1,2 ] , [ [0,1] , [0,2] , [1,0] , [1,2] , [2,0] , [2,1] ] , [... size 3 sets ] ]

into this simplified array :

[ 0 , 1 , 2 , [0,1] , [0,2] , [1,0] , [1,2] , [2,0] , [2,1] , .... size 3 sets ]

and after a Sorting function (that you would have to write) :

[ 0 , [0,1] , [0,2] , [0,1,2] , [0,2,1] , 1 , [1,0] , [1,2] , [1,0,2] , 2 , [2,0] , [2,1] , [2,0,1] , [2, 1,0] ]

Good luck

Edited May 3, 2008 by MikeP