String Permutation (RAM Efficient)

nullschritt · February 7, 2014

Hello, got bored and wrote a script to see how efficiently I could enumerate all possible combinations of a set of data(I was watching Elysium and saw the 4-digit lock cracking program spider user near the end, and got inspired).

[Note: Though the idea was inspired by use of such a program to crack a lock, I please ask you don't use my code to try to crack any locks/passwords, fun/education only please!]

Below is an example that fetches all the possible combinations of the digits 0-9. It takes about 60 seconds, which is pretty good consider it has to do 157,464 calculations.

I believe this is the fastest method of permuting data. It's also extremely efficient on ram, as it only remembers the viable results, not all results of all calculations.

I wish there was some way to support more or less length, but as far as I can tell there is no way to do this(I don't think you can have a dynamic amount of nested loops), if you have a way, I welcome you to show me. [if you want it to use more or less length, just add/remove for loops and values as necessary]

#include <Array.au3>

_ArrayDisplay(_permute_4('0123456789'))

func _permute_4($string)
Local $permuted = '',  $sourcearray, $aArray, $aNewArray, $opcount = 0

$sourcearray = StringSplit($string, "")
$timer = TimerInit()
for $i = 1 to $sourcearray[0]
    for $i2 = 1 to $sourcearray[0]
        for $i3=1 to $sourcearray[0]
            for $i4=1 to $sourcearray[0]
                if $i=$i2 and $i2 = $i3 and $i3 = $i4 Then
                    $permuted&="|"&$sourcearray[$i]&$sourcearray[$i2]&$sourcearray[$i3]&$sourcearray[$i4]
                    $opcount +=1
                Else
                if StringRegExp($permuted, "(.*?)("&$sourcearray[$i]&$sourcearray[$i2]&$sourcearray[$i3]&$sourcearray[$i4]&")(.*?)") Then
                ConsoleWrite("Data already permuted"&@CRLF)
                Else
                Local $aArray[4] = [$sourcearray[$i], $sourcearray[$i2], $sourcearray[$i3], $sourcearray[$i4]]
                Local $aNewArray = _ArrayPermute($aArray) ;Using Default Parameters
                                $opcount +=30
                for $ix=1 to 24
                    if Not StringRegExp($permuted, "(.*?)("&$aNewArray[$ix]&")(.*?)") and $aNewArray[$ix] <> "" Then
                    $permuted &= '|'&$aNewArray[$ix]
                    ConsoleWrite(StringLen($permuted)/5&@CRLF)
                    EndIf
                $opcount +=1
                Next
                EndIf
                EndIf
            Next
        Next
    Next
Next
$time = TimerDiff($timer)
ConsoleWrite("Took "&$time&" MS for "&$opcount&' operations.'&@CRLF)
$permuted = StringSplit(StringTrimLeft($permuted,1), "|")
return $permuted
EndFunc

Edited February 7, 2014 by nullschritt

jchd · February 7, 2014

A 4-digit lock having 157464 combinations? :think:

spudw2k · February 7, 2014

Wouldn't it be 0000 - 9999 (10000 possibilities)?
It would be even less if there could only be one of each digit in the code, but that's too much math for me this early.

Fun concept though.

edit:

It would be even less if there could only be one of each digit in the code...

5040

#include <Array.au3>

Local $hTimer = TimerInit()
Local $a = _Permute_4('012345')
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")


; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed)
    Local $aArray, $aNewArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    $iUB = UBound($aArray)
    ;Local $aNewArray[$iUB * $iUB * $iUB * $iUB] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    Local $aNewArray[1]
    Local $indx=0
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            If Not StringInstr($aArray[$i],$aArray[$j]) Then
                For $k = 0 To $iUB - 1
                    If Not StringInstr($aArray[$j]&$aArray[$i],$aArray[$k]) Then
                        For $m = 0 To $iUB - 1
                            If Not StringInstr($aArray[$k]&$aArray[$j]&$aArray[$i],$aArray[$m]) Then
                                ;$aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                                ReDim $aNewArray[$indx+1]
                                $indx += 1
                                $aNewArray[$indx-1] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                            EndIf
                        Next
                    EndIf
                Next
            EndIf
        Next
    Next
    Return $aNewArray
EndFunc   ;==>_Permute_4

Edited February 7, 2014 by spudw2k

Malkey · February 7, 2014

Here is another method without any regular expressions in the middle For...Next loop.

#include <Array.au3>

Local $hTimer = TimerInit()
Local $a = _Permute_4('0123456789')
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")


; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed)
    Local $aArray, $aNewArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    $iUB = UBound($aArray)
    Local $aNewArray[$iUB * $iUB * $iUB * $iUB] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
    Return $aNewArray
EndFunc   ;==>_Permute_4

nullschritt · February 7, 2014

A 4-digit lock having 157464 combinations?

It doesn't have 157,464 combinations, that's simply how many times 4 nested loops runs, estimating all combinations of 10 values, at 4 digits in length.

If you run the code you'll see it only returns 10,000 results. Most of the time is spent making sure that no values overlap from a previously permuted string.

nullschritt · February 7, 2014

Here is another method without any regular expressions in the middle For...Next loop.

#include <Array.au3>

Local $hTimer = TimerInit()
Local $a = _Permute_4('0123456789')
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")


; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed)
    Local $aArray, $aNewArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    $iUB = UBound($aArray)
    Local $aNewArray[$iUB * $iUB * $iUB * $iUB] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
    Return $aNewArray
EndFunc   ;==>_Permute_4

I was trying to do something similar to this but couldn't figure it out. Wow. That's impressively fast!

Edit: Could you explain the math going on the calculates the position of the new string? I would like to test it with longer amounts of data.

Edited February 7, 2014 by nullschritt

jchd · February 7, 2014

I don't get it:

#include <Array.au3>

Local $hTimer = TimerInit()
Local $a
_Permute_4('0123456789', $a)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")

$hTimer = TimerInit()
Local $b
_inc4($b)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($b, "Array Permuted")

Func _inc4(ByRef $b)
    Dim $b[10^4]
    For $i = 0 To UBound($b) - 1
        $b[$i] = StringRight("000" & $i, 4)
    Next
EndFunc

Exit

; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed, ByRef $aNewArray)
    Local $aArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    $iUB = UBound($aArray)
    Dim $aNewArray[$iUB ^ 4] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
EndFunc   ;==>_Permute_4

Edit: I was displaying $a twice, but anyway.

Edited February 7, 2014 by jchd

nullschritt · February 7, 2014

I don't get it:

#include <Array.au3>

Local $hTimer = TimerInit()
Local $a
_Permute_4('0123456789', $a)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")

$hTimer = TimerInit()
Local $b
_inc4($b)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")

Func _inc4(ByRef $b)
    Dim $b[10^4]
    For $i = 0 To UBound($b) - 1
        $b[$i] = StringRight("000" & $i, 4)
    Next
EndFunc

Exit

; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed, ByRef $aNewArray)
    Local $aArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    $iUB = UBound($aArray)
    Dim $aNewArray[$iUB ^ 4] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
EndFunc   ;==>_Permute_4

It calculates more than just 10 digits. You can put any set of data into it to be permuted. you could for example use 'abcdefghijklmnopqrstuvwxyz' to get all 4 character combinations of the alphabet/

jchd · February 7, 2014

OK:

#include <Array.au3>

Local $set = 'abcdefghijklmnopqrstuvwxyz'
Local $hTimer = TimerInit()
Local $a
_Permute_4($set, $a)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")

$hTimer = TimerInit()
Local $b
_inc4($set, $b)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($b, "Array Permuted")

Func _inc4($charset, ByRef $b)
    Local $n = StringLen($charset)
    Dim $b[$n ^ 4]
    Local $chars = StringSplit($charset, '', 2)
    For $i = 0 To UBound($b) - 1
        $b[$i] = $chars[Mod($i/$n^3, $n)] & $chars[Mod($i/$n^2, $n)] & $chars[Mod($i/$n, $n)] & $chars[Mod($i, $n)]
    Next
EndFunc

Exit

; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed, ByRef $aNewArray)
    Local $aArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    Local $iUB = UBound($aArray)
    Dim $aNewArray[$iUB ^ 4] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
EndFunc   ;==>_Permute_4

nullschritt · February 7, 2014

OK:

#include <Array.au3>

Local $set = 'abcdefghijklmnopqrstuvwxyz'
Local $hTimer = TimerInit()
Local $a
_Permute_4($set, $a)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")

$hTimer = TimerInit()
Local $b
_inc4($set, $b)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($b, "Array Permuted")

Func _inc4($charset, ByRef $b)
    Local $n = StringLen($charset)
    Dim $b[$n ^ 4]
    Local $chars = StringSplit($charset, '', 2)
    For $i = 0 To UBound($b) - 1
        $b[$i] = $chars[Mod($i/$n^3, $n)] & $chars[Mod($i/$n^2, $n)] & $chars[Mod($i/$n, $n)] & $chars[Mod($i, $n)]
    Next
EndFunc

Exit

; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed, ByRef $aNewArray)
    Local $aArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    Local $iUB = UBound($aArray)
    Dim $aNewArray[$iUB ^ 4] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
EndFunc   ;==>_Permute_4

Smart. Significant preformance impact. I tried to beef it up to 6 digits but I got an error saying the maximum array size was exceeded

jchd · February 8, 2014

AutoIt arrays have a limit of 16 millions cells, which (as I just tested) is in fact 16 * 1024 * 1024 = 16 777 216.

26⁶ = 308 915 776

UEZ · February 8, 2014

Here a recursion variant of permutation (at least what I understand of the word permutation):

#include <Array.au3>

Global $string = "ABCD", $perms = 0
Permutator(1, StringLen($string), $string)
ConsoleWrite("Permutation: " & $perms & @LF)

Func Permutator($a, $b, $s) ;coded by UEZ 2014
    If $a = $b Then
        ConsoleWrite($s & @CRLF)
        $perms += 1
    Else
        Local $aChars = StringSplit($s, ""), $t, $i
        For $i = $a to $b
            $t = $aChars[$a]
            $aChars[$a] = $aChars[$i]
            $aChars[$i] = $t
            Permutator($a + 1, $b, _ArrayToString($aChars, "", 1))
        Next
    EndIf
EndFunc

Recusion is unfortunatelly limited to the recursion stack size!

Br,
UEZ

Edited February 8, 2014 by UEZ

nullschritt · February 8, 2014

Here a recursion variant of permutation (at least what I understand of the word permutation):

#include <Array.au3>

Global $string = "ABCD", $perms = 0
Permutator(1, StringLen($string), $string)
ConsoleWrite("Permutation: " & $perms & @LF)

Func Permutator($a, $b, $s) ;coded by UEZ 2014
    If $a = $b Then
        ConsoleWrite($s & @CRLF)
        $perms += 1
    Else
        Local $aChars = StringSplit($s, ""), $t, $i
        For $i = $a to $b
            $t = $aChars[$a]
            $aChars[$a] = $aChars[$i]
            $aChars[$i] = $t
            Permutator($a + 1, $b, _ArrayToString($aChars, "", 1))
        Next
    EndIf
EndFunc

Recusion is unfortunatelly limited to the recursion stack size!

Br,

UEZ

Seems efficient but the length of the data should be independent of the length of possible data. (eg we should be able to set it to 4 digits even if the data set is 10 long)

jchd · February 8, 2014

Unfortunately Execute takes exponential time over the complexity of fed instruction (i.e. be patient!):

#include <Array.au3>

Local $set = 'abcdefghijkl'
Local $hTimer = TimerInit()
Local $a
_Permute_4($set, $a)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($a, "Array Permuted")

$hTimer = TimerInit()
Local $b
_incN($set, 5, $b)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)

_ArrayDisplay($b, "Array Permuted")

Func _incN($charset, $size, ByRef $b)
    Local $chars
    #forceref $chars
    $size = Int($size)
    If $size < 1 Then Return(SetError(1))
    Local $n = StringLen($charset)
    If $n ^ $size > 16 * 1024 * 1024 Then Return(SetError(2))
    Dim $b[$n ^ $size]
    $chars = StringSplit($charset, '', 2)
    Local $inst
    For $i = $size To 2 Step -1
        $inst &= "$chars[Mod($i/$n^" & $i & ", $n)] & "
    Next
    $inst &= "$chars[Mod($i, $n)]"
    For $i = 0 To UBound($b) - 1
        $b[$i] = Execute($inst)
    Next
EndFunc



Exit

; Returns all possible combinations of 4 characters out of $sCharsToBeUsed, the list of all possible characters from which to select.
Func _Permute_4($sCharsToBeUsed, ByRef $aNewArray)
    Local $aArray
    $aArray = StringSplit($sCharsToBeUsed, "", 2)
    Local $iUB = UBound($aArray)
    Dim $aNewArray[$iUB ^ 4] ; 4 digits, with each digit can be 0 to 9 (each digit has 10 possibilities)
    For $i = 0 To $iUB - 1
        For $j = 0 To $iUB - 1
            For $k = 0 To $iUB - 1
                For $m = 0 To $iUB - 1
                    $aNewArray[($i * ($iUB ^ 3)) + ($j * ($iUB ^ 2)) + ($k * $iUB) + $m] = $aArray[$i] & $aArray[$j] & $aArray[$k] & $aArray[$m]
                Next
            Next
        Next
    Next
EndFunc   ;==>_Permute_4

Edited February 8, 2014 by jchd

wraithdu · February 8, 2014

I wrote this a while back. Just added a callback option for result sets that would be too big for an array.

#include-once
; #FUNCTION# ;===================================================================================================================
; Name...........: _DuplicatePermute
; Description ...: Returns an array of permutations (incl duplicates) of a given length from items in an array
; Syntax.........: _DuplicatePermute(Const Byref $aArray, $iLen[, $sDelim = ""[, $cFunc = Default]])
; Parameters ....: $aArray         - The array to get permutations
;                  $iLen           - Length of each permutation
;                  $sDelim         - [optional] String result separator, default is "" for none
;                  $cFunc          - [optional] Callback function to be called with each permutation. The function will be
;                                    called with 3 parameters:
;                                        1 - count of current permutation
;                                        2 - count of total permutations
;                                        3 - current permutation as a string
;                                    The function must return non-zero to continue.
; Return values .: Success - Returns an Array of permutations (incl duplicates)
;                  Returns an array, the first element ($array[0]) contains the number of strings returned. If $cFunc is Default,
;                  the remaining elements ($array[1], $array[2], etc.) contain the permutations. Otherwise the return array has
;                  2 elements and $array[1] contains the number of permutations processed.
;                  Failure - Returns 0 and Sets @error:
;                  1 - The input must be an array
;                  2 - The function stopped before processing all permutations
; Author ........: Erik Pilsits
; Modified.......: 02/07/2014
; Remarks .......: The input array must be 0-based, ie no counter in $array[0]
;                  Based on an algorithm by Sandro Magi
; Related .......:
; Link ..........: http://higherlogics.blogspot.com/2008/04/permutations-with-duplicates-in-c.html
;
; Example .......:
; ===============================================================================================================================
Func _DuplicatePermute(Const ByRef $aArray, $iLen, $sDelim = "", $cFunc = Default)
    If Not IsArray($aArray) Then
        Return SetError(1, 0, 0)
    EndIf

    Local Const $n = UBound($aArray)
    Local $avSlots[$iLen], $i, $avResult, $count, $total

    $total = $n ^ $iLen
    If $cFunc = Default Then
        Local $avResult[$total + 1]
        $avResult[0] = $total
    Else
        Local $avResult[2] = [$total]
    EndIf
    $count = 1
    For $i = 0 To $iLen - 1
        $avSlots[$i] = 0
    Next
    While _DuplicateInternal($aArray, $avSlots, $iLen, $n, $sDelim, $avResult, $count, $total, $cFunc)
    WEnd
    Local $err = @error
    If $cFunc <> Default Then $avResult[1] = $count
    Return SetError($err, 0, $avResult)
EndFunc   ;==>_DuplicatePermute

Func _DuplicateInternal(Const ByRef $aArray, ByRef $avSlots, $iLen, $n, $sDelim, ByRef $avResult, ByRef $count, $total, $cFunc)
    Local $i, $b, $carry = 1, $str = ""

    For $i = 0 To $iLen - 1
        $str &= $aArray[$avSlots[$i]] & $sDelim
    Next
    If $sDelim <> "" Then $str = StringTrimRight($str, 1)
    If $cFunc = Default Then
        $avResult[$count] = $str
    Else
        If Not $cFunc($count, $total, $str) Then Return SetError(2, 0, 0)
    EndIf
    $count += 1

    For $i = 0 To $iLen - 1
        $b = $avSlots[$i] + $carry
        $carry = Int($b / $n)
        $avSlots[$i] = Mod($b, $n)
    Next
    Return Not $carry
EndFunc   ;==>_DuplicateInternal

Example

#include <Array.au3>
#include <_DuplicatePermute.au3>

Global $a = StringSplit("0123456789", "", 2)
$b = _DuplicatePermute($a, 3, "")
_ArrayDisplay($b)
$b = _DuplicatePermute($a, 3, "", myfunc)
_ArrayDisplay($b)

Func myfunc($c, $t, $s)
    ConsoleWrite($c & " : " & $t & " : " & $s & @CRLF)
    If $c > 9 Then
        Return 0
    Else
        Return 1
    EndIf
EndFunc

Not tested for speed, but I think it's pretty good. It's iterative too, so no worries about hitting the recursion limit.

Edited February 8, 2014 by wraithdu

Gianni · February 8, 2014

#include <array.au3>
Global $string = "ABCDE"
$hTimer = TimerInit()
Local $chars = StringSplit($string, '', 2)
Local $Permutations = _ArrayPermute($chars)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)
_ArrayDisplay($Permutations)

Edited February 8, 2014 by PincoPanco

wraithdu · February 8, 2014

That's actually my function also. Difference is though, that version doesn't produce duplicates, so you won't get 0000, 1111, 0011, etc. It also only uses the full data set, so you can't do permutations of 4 elements out of a set of 10.

nullschritt · February 8, 2014

#include <array.au3>
Global $string = "ABCDE"
$hTimer = TimerInit()
Local $chars = StringSplit($string, '', 2)
Local $Permutations = _ArrayPermute($chars)
ConsoleWrite("Time Taken: " & Round(TimerDiff($hTimer) / 1000, 3) & "secs" & @CRLF)
_ArrayDisplay($Permutations)

As stated this results in replicates and only produces data the length of the input data. You'll see my very first example uses the _arraypermute() function inside of several loops(with regexs) to simulate support for say x chars in a set of 4 digits, without repeating digits, though the other posts are considerably quicker!

wraithdu · February 8, 2014

If you want no repeating digits, then use _ArrayPermute along with _ArrayCombinations to permute each unique combination. The UDF functions aren't written with array size in mind, so be careful about the size of your result set. Example:

#include <Array.au3>

Global $a = StringSplit("0123456789", "", 2)
Global $b = _ArrayCombinations($a, 4)
Global $c, $d, $e[1] = [0]
For $i = 1 To $b[0]
    ; get combination and create array
    $c = StringSplit($b[$i], "", 2)
    ; permute
    $d = _ArrayPermute($c)
    ; build result
    $e[0] += $d[0]
    _ArrayConcatenate($e, $d, 1)
Next
_ArrayDisplay($e)

Sign In

String Permutation (RAM Efficient)

Recommended Posts

nullschritt

jchd

spudw2k

Malkey

nullschritt

nullschritt

jchd

nullschritt

jchd

nullschritt

jchd

UEZ

nullschritt

jchd

wraithdu

Gianni

wraithdu

nullschritt

wraithdu

Create an account or sign in to comment

Create an account

Sign in

Similar Content

Reverse _ArrayToString - (Moved)

Comparing two strings with various parameters and get Percentage of matching

String Trigger

Getting all permutations of Nested Spintax?

How to convert String to Array without any delimiters?

Browse

AutoIt Resources

Release

Beta