_ArrayPermute() UDF

[litlmike]

There have been several requests for a permutation function, especially for one that can parse strings longer than 1 character, so I decided to attempt creating a UDF that allows for this. This is based off of /dev/null's previous work on permutations, with some upgrades, and uses the current <Array.au3>.

Currently its main function is to take a list of strings (from an array), permutate those strings, sort and display. User can alter several parameters affecting how the output is displayed. Please test and provide as much feedback as possible, as my goal is to get this included into the AutoIt library. I will fix bugs as often as possible. I am also considering either modifying or creating new functions to generate combinations and variations, so any direction is welcome.

Edits:

01/22/2009

Made Improvements to _ArrayCombinationsInternal() based upon suggestions from bchris01

New .Zip File for Download

08/05/2008

Fixed a typo

07/16/2008

Removed the use of _ArrayAdd to enhance performance (done by wraithdu). New downloads. Removed the Funcs from original post, now just in the downloadable attachment.

07/15/2008

Based upon the feedback of wraithdu: re-worked _ArrayPermute and added _ArrayCombinations. Download below.

06/26/2008

Added the ability to select an Array Range, and an example

06/24/2008

UDF with Examples:

Downloaded 122 times

Download:

Array.zip

Edited January 23, 2009 by litlmike

[TehWhale]

This deserve to be in Array.au3 included in the AutoIt v3 Install set.

[litlmike]

This deserve to be in Array.au3 included in the AutoIt v3 Install set.

Thanks, I really appreciate that.

[jvanegmond]

This is pretty good. I'm sure you checked out some of the other permutations (you said that was based on /dev/null's), but just as a list of reference I am posting them here.

http://www.autoitscript.com/forum/index.php?showtopic=43763

http://www.autoitscript.com/forum/index.ph...mp;#entry325332

[ptrex]

@litlmike

Very Nice !!

Regards,

ptrex

[litlmike]

Thanks to everyone for the positive feedback. Are there any changes that should be made?

[litlmike]

Added the ability to select an Array Range, and an example

[litlmike]

Anyone have any criticism for this UDF, positive or negative?

[wraithdu]

Nice. It would be useful to be able to specify the length of the permutations you want, for example permutations made of 3 strings from a list of 10 strings.

[wraithdu]

I realized what I asked would be an entirely new function to return Array Combinations.....so I wrote one. It is adapted from some javascript code I found, and works very well.

Some suggestions for your UDF first (in the name of speed) -

1. Make the brackets totally optional instead of adding them even if they are blank.

2. Skip the tooltips, that should be part of someone's script, not a UDF

3. Replace the _ArrayReverse / Pop / Add / Reverse with '$aPermutations[0] = UBound($aPermutations) - 1' - much faster

4. Consider removing the _ArrayDisplay as well, at the very least make it default to False. That should also be part of a script, not a UDF.

5. Add an #include-once and #include <Array.au3> to the top of your UDF.

So here's the Combinations function and combined example -

expandcollapse popup

#include-once
#include <Array.au3>
; #FUNCTION# ;==============================================================================================
; Name...........:  _ArrayCombinations
; Description ...:  Returns an Array of the Combinations of a Set of Elements from a Selected Array
; Syntax.........:  _ArrayCombinations(ByRef $avArray, $iSet[, $sDelim = "|"])
; Parameters ....:  $avArray        - The Array to get Combinations
;                   $iSet           - Size of the combinations set
;                   $sDelim         - [optional] String result separator, "" for none
; Return values .:  Success - Returns an Array of '|' delimited Combinations
;                   Returns an array, the first element ($array[0]) contains the number of strings returned.
;                   The remaining elements ($array[1], $array[2], etc.) contain the Combinations.
;                   Failure - Returns 0 and Sets @error:
;                   1 - The Input Must be an Array
; Author ........:  Erik Pilsits
; Modified.......:  07/07/2008
; Remarks .......:  The input array must be 0-based, ie no counter in $array[0]
; Related .......:  _ArrayPermute.au3
; Link ..........:
;
; Example .......:  _ArrayCombinations($array, 4)
;
; ==========================================================================================================
Global $iN, $iR, $iTotal, $iLeft, $aIdx[1]

Func _ArrayCombinations(ByRef $avArray, $iSet, $sDelim = "|")
    Local $i, $sComb, $aResult[1]
    
    If Not IsArray($avArray) Then
        Return SetError(1, 0, 0)
    EndIf
    
    $iTotal = _Combinations($avArray, $iSet)
    $iLeft = $iTotal
    
    While $iLeft > 0
        _GetNext() ; new indices in array $aIdx
        $sComb = ""
        For $i = 0 To $iSet - 1
            $sComb = $sComb & $avArray[$aIdx[$i]] & $sDelim
        Next
        If $sDelim <> "" Then $sComb = StringTrimRight($sComb, 1)
        _ArrayAdd($aResult, $sComb)
    WEnd
    $aResult[0] = UBound($aResult) - 1
    Return $aResult
EndFunc

Func _Combinations(ByRef $avArray, $iSet)
    Local $i, $iNFact = 1, $iRFact = 1, $iNRFact = 1
    
    $iN = UBound($avArray)
    $iR = $iSet
    
    Dim $aIdx[$iR]
    For $i = 0 To $iR - 1
        $aIdx[$i] = $i
    Next
    
    For $i = $iN To 2 Step -1
        $iNFact *= $i
    Next
    For $i = $iR To 2 Step -1
        $iRFact *= $i
    Next
    For $i = $iN - $iR To 2 Step -1
        $iNRFact *= $i
    Next
    Return $iNFact / ($iRFact * $iNRFact)
EndFunc

Func _GetNext()
    Local $i, $j
    
    If $iLeft == $iTotal Then
        $iLeft -= 1
        Return $aIdx
    EndIf
    
    $i = $iR - 1
    While $aIdx[$i] == $iN - $iR + $i
        $i -= 1
    WEnd
    
    $aIdx[$i] += 1
    For $j = $i + 1 To $iR - 1
        $aIdx[$j] = $aIdx[$i] + $j - $i
    Next
    
    $iLeft -= 1
EndFuncoÝ÷ Ø Ýjw±jjezÚ zÖ¥«ëZ¶*'²øzW¦z{l~º&k§¥zg§µªëk&®¶­sb6æ6ÇVFRfÇCµô'&6öÖ&æFöç2æS2fwC°¢6æ6ÇVFRfÇCµô'&W&×WFRæS2fwC° ¤vÆö&Âb33c¶Æ7E³eÒÂb33c¶&W7VÇE³ÒÂb33c¶W&ÕFV׳ÒÂb33c¶W&ճР¢b33c¶Æ7E³ÒÒ¢b33c¶Æ7E³ÒÒ ¢b33c¶Æ7E³%ÒÒ0¢b33c¶Æ7E³5ÒÒ@¢b33c¶Æ7E³EÒÒP¢b33c¶Æ7E³UÒÒ` ¢b33c¶&W7VÇBÒô'&6öÖ&æFöç2b33c¶Æ7BÂB ¤f÷"b33c¶ÒFòb33c¶&W7VÇE³Ð b33c¶W&ÕFV×Òô'&W&×WFR7G&æu7ÆBb33c¶&W7VÇE²b33c¶ÒÂgV÷C·ÂgV÷C²Â2ÂÂgV÷C²gV÷C²ÂÂgV÷C²gV÷C²ÂgV÷C²gV÷C² ô'&FVÆWFRb33c¶W&ÕFV× ô'&6öæ6FVæFRb33c¶W&ÒÂb33c¶W&ÕFVפæW@¢b33c¶W&ÕFV×Ò¢b33c¶W&Õ³ÒÒT&÷VæBb33c¶W&ÒÒ¥ô'&6÷'Bb33c¶W&ÒÂÂ¥ô'&F7Æb33c¶W&Ò

Edited July 8, 2008 by wraithdu

[wraithdu]

So while working around with the Combinations, I found some algorithms for Permutations as well, and thought I'd adapt them and test for speed against devnull's. Here are all the UDF's (incl. a slightly rewritten Combinations UDF to get rid of the need for Global vars), the example, and the speed test.

As you can see, devnull's method is in last place by a HUGE margin, sorry muttley Too bad I can't take credit for the math

Combinations UDF:

expandcollapse popup

#include-once
#include <Array.au3>
; #FUNCTION# ;==============================================================================================
; Name...........:  _ArrayCombinations
; Description ...:  Returns an Array of the Combinations of a Set of Elements from a Selected Array
; Syntax.........:  _ArrayCombinations(ByRef $avArray, $iSet[, $sDelim = ""])
; Parameters ....:  $avArray        - The Array to get Combinations
;                   $iSet           - Size of the combinations set
;                   $sDelim         - [optional] String result separator, default is "" for none
; Return values .:  Success - Returns an Array of Combinations
;                   Returns an array, the first element ($array[0]) contains the number of strings returned.
;                   The remaining elements ($array[1], $array[2], etc.) contain the Combinations.
;                   Failure - Returns 0 and Sets @error:
;                   1 - The Input Must be an Array
; Author ........:  Erik Pilsits
; Modified.......:  07/07/2008
; Remarks .......:  The input array must be 0-based, ie no counter in $array[0]
;                   Based on an algorithm by Kenneth H. Rosen.
; Related .......:  _ArrayPermute.au3
; Link ..........:  http://www.merriampark.com/comb.htm
;
; Example .......:  _ArrayCombinations($array, 4)
;
; ==========================================================================================================
Func _ArrayCombinations(ByRef $avArray, $iSet, $sDelim = "")
    Local $i, $sComb, $aIdx[1], $aResult[1], $iN = 0, $iR = 0, $iLeft = 0, $iTotal = 0
    
    If Not IsArray($avArray) Then
        Return SetError(1, 0, 0)
    EndIf
    
    $iN = UBound($avArray)
    $iR = $iSet
    Dim $aIdx[$iR]
    For $i = 0 To $iR - 1
        $aIdx[$i] = $i
    Next
    $iTotal = _Combinations($iN, $iR)
    $iLeft = $iTotal
    
    While $iLeft > 0
        _GetNext($iN, $iR, $iLeft, $iTotal, $aIdx)
        $sComb = ""
        For $i = 0 To $iSet - 1
            $sComb = $sComb & $avArray[$aIdx[$i]] & $sDelim
        Next
        If $sDelim <> "" Then $sComb = StringTrimRight($sComb, 1)
        _ArrayAdd($aResult, $sComb)
    WEnd
    $aResult[0] = UBound($aResult) - 1
    Return $aResult
EndFunc

Func _Combinations($iN, $iR)
    Local $i, $iNFact = 1, $iRFact = 1, $iNRFact = 1
    
    For $i = $iN To 2 Step -1
        $iNFact *= $i
    Next
    For $i = $iR To 2 Step -1
        $iRFact *= $i
    Next
    For $i = $iN - $iR To 2 Step -1
        $iNRFact *= $i
    Next
    Return $iNFact / ($iRFact * $iNRFact)
EndFunc

Func _GetNext($iN, $iR, ByRef $iLeft, $iTotal, ByRef $aIdx)
    Local $i, $j
    
    If $iLeft == $iTotal Then
        $iLeft -= 1
        Return $aIdx
    EndIf
    
    $i = $iR - 1
    While $aIdx[$i] == $iN - $iR + $i
        $i -= 1
    WEnd
    
    $aIdx[$i] += 1
    For $j = $i + 1 To $iR - 1
        $aIdx[$j] = $aIdx[$i] + $j - $i
    Next
    
    $iLeft -= 1
EndFuncoÝ÷ ØL^µêÏz¹®µ«b¢p%ⶺÚ"µÍÚ[ÛYK[ÛÙBÚ[ÛYH  Ð^K]LÉÝÂÈÑSÕSÓÈÏOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOBÈ[YKWÑ^]]]BÈØÜ[ÛT]È[^HÙH]]][ÛÈÙ[[[Y[È[[^BÈÞ[^WÑ^]]]JTY   ÌÍØ]^VË ÌÍÜÑ[[HH    ][ÝÉ][Ý×JBÈ[Y]ÈIÌÍØ]^BBKHH^HÈÙ]]]][ÛÂÂBBBBIÌÍÜÑ[[BBBKHÛÜ[Û[HÝ[ÈÝ[Ù]ÜY][È ][ÝÉ][ÝÈÜÛBÈ][YÈTÝXØÙÜÈH]È[^HÙ]]][ÛÂÈT]È[^KHÝ[[Y[
    ÌÍØ^VÌJHÛÛZ[ÈH[XÙÝ[ÜÈ]YÈUH[XZ[[È[[Y[È
    ÌÍØ^VÌWK    ÌÍØ^VÌK]ËHÛÛZ[H]]][ÛËÈQZ[HH]È[Ù]ÈÜÈLHHH[]]ÝH[^BÈ]]ÜQZÈ[Ú]ÂÈ[ÙYYYL
ËÌÌÈ[XÜÈUH[]^H]ÝHXÙYYHÈÛÝ[[  ÌÍØ^VÌBÂBBBBPÙYÛ[[ÛÜ]HÛH^][]Ú]KÈ[]YWÐÙÛÛ[ÛT]]K]LÂÈ[ÈZËÝÝÝËXØ]KÛÛKÜ[ÛWÚXÚÜËÜ]]K[ÂÈ^[HWÑ^]]]J   ÌÍØ^JBÂÈOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOB[ÈÑ^]]]JTY ÌÍØ]^K   ÌÍÜÑ[[HH    ][ÝÉ][ÝÊBSØØ[ ÌÍÚK ÌÍÚTÚ^HHPÝ[
    ÌÍØ]^JK  ÌÍØRYÉÌÍÚTÚ^WK  ÌÍØTÝ[ÌWBBRYÝÐ^J ÌÍØ]^JH[BT]Ù]ÜK
BQ[YBQÜ    ÌÍÚHHÈ  ÌÍÚTÚ^HHBBIÌÍØRYÉÌÍÚWHH  ÌÍÚBS^WÑ^][[
    ÌÍØ]^K   ÌÍÚTÚ^K ÌÍÜÑ[[K ÌÍØRY    ÌÍØTÝ[
BIÌÍØTÝ[ÌHHPÝ[
    ÌÍØTÝ[
HHBT]   ÌÍØTÝ[[[Â[ÈÑ^][[
TY  ÌÍØ]^K   ÌÍÚTÝ   ÌÍÚTÚ^K ÌÍÜÑ[[KTY   ÌÍØRYTY  ÌÍØTÝ[
BSØØ[ ÌÍÚK ÌÍÜÕ[H  ][ÝÉ][ÝË    ÌÍÚU[BRY ÌÍÚTÝOH ÌÍÚTÚ^HHH[BQÜ  ÌÍÚHHÈ  ÌÍÚTÚ^HHBBBIÌÍÜÕ[   [ÏH    ÌÍØ]^VÉÌÍØRYÉÌÍÚWWH  [È ÌÍÜÑ[[BBS^BRY   ÌÍÜÑ[[H ÉÝÈ  ][ÝÉ][ÝÈ[   ÌÍÜÕ[HÝ[Õ[TYÚ
    ÌÍÜÕ[JBBWÐ^PY
    ÌÍØTÝ[  ÌÍÜÕ[
BQ[ÙBBQÜ  ÌÍÚHH    ÌÍÚTÝÈ ÌÍÚTÚ^HHBBBIÌÍÚU[H   ÌÍØRYÉÌÍÚWBBBBBBIÌÍØRYÉÌÍÚWHH ÌÍØRYÉÌÍÚTÝBBBIÌÍØRYÉÌÍÚTÝHH    ÌÍÚU[BBWÑ^][[
    ÌÍØ]^K   ÌÍÚTÝ
ÈK ÌÍÚTÚ^K ÌÍÜÑ[[K ÌÍØRY    ÌÍØTÝ[
BBBIÌÍØRYÉÌÍÚTÝHH   ÌÍØRYÉÌÍÚWBBBIÌÍØRYÉÌÍÚWHH    ÌÍÚU[BS^Q[Y[[oÝ÷ Ø ¢j%#Þ®k­jب  `¢¸­f®¶­sb6æ6ÇVFRÖöæ6P¢6æ6ÇVFRfÇC´'&æS2fwC°£²4eTä5Dôâ2³ÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓУ²æÖRââââââââââã¢ô&övöÖöÆçW&×WFP£²FW67&Föâââã¢&WGW&ç2â'&öbFRW&×WFFöç2öbÆÂVÆVÖVçG2ââ'&£²7çFââââââââã¢ô&övöÖöÆçW&×WFR'&Vbb33c¶d'&²Âb33c·4FVÆÒÒgV÷C²gV÷CµÒ£²&ÖWFW'2âââã¢b33c¶d'&ÒFR'&FòvWBW&×WFFöç0£°b33c·4FVÆÐÒ¶÷FöæÅÒ7G&ær&W7VÇB6W&F÷"ÂFVfVÇB2gV÷C²gV÷C²f÷"æöæP£²&WGW&âfÇVW2ã 7V66W72Ò&WGW&ç2â'&öbW&×WFFöç0£²&WGW&ç2â'&ÂFRf'7BVÆVÖVçBb33c¶'&³Ò6öçFç2FRçVÖ&W"öb7G&æw2&WGW&æVBࣲFR&VÖæærVÆVÖVçG2b33c¶'&³ÒÂb33c¶'&³%ÒÂWF2â6öçFâFRW&×WFFöç2ࣲfÇW&RÒ&WGW&ç2æB6WG2W'&÷# £²ÒFRçWB×W7B&Râ'&£²WF÷"âââââââã¢W&²Ç6G0£²ÖöFfVBââââââã¢róó#£²&VÖ&·2ââââââã FRçWB'&×W7B&RÖ&6VBÂRæò6÷VçFW"âb33c¶'&³Òࣰ&6VBöâFRÆv÷&FÒ'ÆWæFW"&övöÖöÆçࣲ&VÆFVBââââââã ôWWFW%W&×WFRæS0£²Ææ²âââââââââã GG¢ò÷wwræ&V&6fRæ6öÒ÷&æFöÕö6·2÷W&×WFRæFÖÀ£°£²W×ÆRââââââã ô&övöÖöÆçW&×WFRb33c¶'&£°£²ÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓФgVæ2ô&övöÖöÆçW&×WFR'&Vbb33c¶d'&Âb33c·4FVÆÒÒgV÷C²gV÷C² Æö6Âb33c¶Âb33c¶6¦RÒT&÷VæBb33c¶d'&Âb33c¶G²b33c¶6¦UÒÂb33c¶&W7VÇE³ÒÂb33c¶ÆWfVÂÒÓ  bæ÷B4'&b33c¶d'&FVà &WGW&â6WDW'&÷" VæD`  f÷"b33c¶ÒFòb33c¶6¦RÒ b33c¶G²b33c¶ÒÒ æW@ ô&övöÖöÆççFW&æÂb33c¶d'&ÂÂb33c¶6¦RÂb33c·4FVÆÒÂb33c¶GÂb33c¶&W7VÇBÂb33c¶ÆWfV b33c¶&W7VÇE³ÒÒT&÷VæBb33c¶&W7VÇBÒ &WGW&âb33c¶&W7VÇ@¤VæDgVæ0 ¤gVæ2ô&övöÖöÆççFW&æÂ'&Vbb33c¶d'&Âb33c¶7F'BÂb33c¶6¦RÂb33c·4FVÆÒÂ'&Vbb33c¶GÂ'&Vbb33c¶&W7VÇBÂ'&Vbb33c¶ÆWfV Æö6Âb33c¶Âb33c·5FV×ÒgV÷C²gV÷C°  b33c¶ÆWfVÂ³Ò b33c¶G²b33c¶7F'EÒÒb33c¶ÆWfVÀ  bb33c¶ÆWfVÂÓÒb33c¶6¦RFVà f÷"b33c¶ÒFòb33c¶6¦RÒ b33c·5FV×f׳Òb33c¶d'&²b33c¶G²b33c¶ÒÒÒfײb33c·4FVÆÐ æW@ bb33c·4FVÆÒfÇC²fwC²gV÷C²gV÷C²FVâb33c·5FV×Ò7G&æuG&Õ&vBb33c·5FV× ô'&FBb33c¶&W7VÇBÂb33c·5FV× VÇ6P f÷"b33c¶ÒFòb33c¶6¦RÒ bb33c¶G²b33c¶ÒÓÒFVà ô&övöÖöÆççFW&æÂb33c¶d'&Âb33c¶Âb33c¶6¦RÂb33c·4FVÆÒÂb33c¶GÂb33c¶&W7VÇBÂb33c¶ÆWfV VæD` æW@ VæD` b33c¶ÆWfVÂÓÒ b33c¶G²b33c¶7F'EÒÒ¤VæDgVæoÝ÷ Ù*^yÔÞ²Ñ1jje{·¥zg§¶Ë§²íyÙèuébÆ®¶­sb6æ6ÇVFRfÇCµôWWFW%W&×WFRæS2fwC°¢6æ6ÇVFRfÇCµô&övöÖöÆçW&×WFRæS2fwC°¢6æ6ÇVFRfÇCµô'&W&×WFRæS2fwC° ¤vÆö&Âb33c¶'&³uФf÷"b33c¶ÒFòT&÷VæBb33c¶'&Ò b33c¶'&²b33c¶ÒÒb33c¶²¤æW@ ¢b33c·FÖW"ÒFÖW$æB¢b33c¶&W7VÇBÒôWWFW%W&×WFRb33c¶'&¤6öç6öÆUw&FRgV÷C´WWFW#¢gV÷C²fײFÖW$Ffbb33c·FÖW"òfײgV÷C²6V2gV÷C²fײ5$Äb¥ô'&F7Æb33c¶&W7VÇB ¢b33c·FÖW"ÒFÖW$æB¢b33c¶&W7VÇBÒô&övöÖöÆçW&×WFRb33c¶'&¤6öç6öÆUw&FRgV÷C´&övöÖöÆç¢gV÷C²fײFÖW$Ffbb33c·FÖW"òfײgV÷C²6V2gV÷C²fײ5$Äb¥ô'&F7Æb33c¶&W7VÇB ¢b33c·FÖW"ÒFÖW$æB¢b33c¶&W7VÇBÒô'&W&×WFRb33c¶'&ÂÂgV÷C²gV÷C²ÂÂgV÷C²gV÷C²ÂgV÷C²gV÷C²¤6öç6öÆUw&FRgV÷C¶FWfçVÆâgV÷C²fײFÖW$Ffbb33c·FÖW"òfײgV÷C²6V2gV÷C²fײ5$Äb¥ô'&F7Æb33c¶&W7VÇBoÝ÷ Ø[¥÷«ëZ¶*'°LZ^jëh×6#include <_ArrayCombinations.au3>
#include <_ExeterPermute.au3>

Global $sList, $aList, $aResult[1], $aPermTemp[1], $aPerm[1], $aTemp[1]

Dim $aList[5] = [1, 2, 3, 4, 5]

$aResult = _ArrayCombinations($aList, 5, ",")
_ArrayDisplay($aResult, "Combinations")

For $i = 1 To $aResult[0]
    $aTemp = StringSplit($aResult[$i], ",", 3)
    $aPermTemp = _ExeterPermute($aTemp)
    _ArrayDelete($aPermTemp, 0)
    _ArrayConcatenate($aPerm, $aPermTemp)
Next
$aPermTemp = 0
$aPerm[0] = UBound($aPerm) - 1
_ArraySort($aPerm, 0, 1)
_ArrayDisplay($aPerm, "Permutations")

And the results of my permutation speed tests on a 7 element array:

Exeter: 16.0039109020839 sec

Bogomolny: 16.35302259086 sec

devnull: 128.295503129588 sec

Exeter: 16.0464103677981 sec

Bogomolny: 16.3414037258925 sec

devnull: 128.545797231212 sec

Edited July 8, 2008 by wraithdu

[litlmike]

So while working around with the Combinations, I found some algorithms for Permutations as well, and thought I'd adapt them and test for speed against devnull's. Here are all the UDF's (incl. a slightly rewritten Combinations UDF to get rid of the need for Global vars), the example, and the speed test.

As you can see, devnull's method is in last place by a HUGE margin, sorry muttley Too bad I can't take credit for the math

...

Wow nice! What you have here is really great. Sorry I didn't respond sooner, I am supposed to get email notices when a post is made, but it looks it missed yours. Anyways, I took what you made and packaged it for the Au3 install set. Hopefully GaryFrost will include it. Funny to see that you posted that link, I also went there but didn't know how to convert the syntax. Thanks for all of this. Double check my notations to make sure I understood it all correctly.

Thanks!

[wraithdu]

Glad you like it! I hate to do this to you then, but while I was doing some other stuff, I decided to make a small adjustment and see what difference it made. I got rid of the _ArrayAdd() in all the functions. It turns out all the ReDims from the _ArrayAdd() is a HUGE performance hit. Here's the new funcs and speed test results -

Combinations:

expandcollapse popup

#include-once
; #FUNCTION#;=========================================================================================

=====
; Name...........:  _ArrayCombinations
; Description ...:  Returns an Array of the Combinations of a Set of Elements from a Selected Array
; Syntax.........:  _ArrayCombinations(ByRef $avArray, $iSet[, $sDelim = ""])
; Parameters ....:  $avArray        - The Array to get Combinations
;                   $iSet           - Size of the combinations set
;                   $sDelim         - [optional] String result separator, default is "" for none
; Return values .:  Success - Returns an Array of Combinations
;                     Returns an array, the first element ($array[0]) contains the number of strings returned.
;                     The remaining elements ($array[1], $array[2], etc.) contain the Combinations.
;                     Failure - Returns 0 and Sets @error:
;                     1 - The Input Must be an Array
; Author ........:  Erik Pilsits
; Modified.......:  07/07/2008
; Remarks .......:  The input array must be 0-based, ie no counter in $array[0]
;                   Based on an algorithm by Kenneth H. Rosen.
; Related .......:  _ArrayPermute.au3
; Link ..........:  http://www.merriampark.com/comb.htm
;
; Example .......:  _ArrayCombinations($array, 4)
;
; ====================================================================================================


======
Func _ArrayCombinations(ByRef $avArray, $iSet, $sDelim = "")
    Local $i, $sComb, $aIdx[1], $aResult[1], $iN = 0, $iR = 0, $iLeft = 0, $iTotal = 0, $iCount = 1
    
    If Not IsArray($avArray) Then
        Return SetError(1, 0, 0)
    EndIf
    
    $iN = UBound($avArray)
    $iR = $iSet
    Dim $aIdx[$iR]
    For $i = 0 To $iR - 1
        $aIdx[$i] = $i
    Next
    $iTotal = _Combinations($iN, $iR)
    $iLeft = $iTotal
    ReDim $aResult[$iTotal + 1]
    $aResult[0] = $iTotal
    
    While $iLeft > 0
        _GetNext($iN, $iR, $iLeft, $iTotal, $aIdx)
        $sComb = ""
        For $i = 0 To $iSet - 1
            $aResult[$iCount] &= $avArray[$aIdx[$i]] & $sDelim
        Next
        If $sDelim <> "" Then $aResult[$iCount] = StringTrimRight($aResult[$iCount], 1)
        $iCount += 1
    WEnd
    Return $aResult
EndFunc

Func _Combinations($iN, $iR)
    Local $i, $iNFact = 1, $iRFact = 1, $iNRFact = 1
    
    For $i = $iN To 2 Step -1
        $iNFact *= $i
    Next
    For $i = $iR To 2 Step -1
        $iRFact *= $i
    Next
    For $i = $iN - $iR To 2 Step -1
        $iNRFact *= $i
    Next
    Return $iNFact / ($iRFact * $iNRFact)
EndFunc

Func _GetNext($iN, $iR, ByRef $iLeft, $iTotal, ByRef $aIdx)
    Local $i, $j
    
    If $iLeft == $iTotal Then
        $iLeft -= 1
        Return
    EndIf
    
    $i = $iR - 1
    While $aIdx[$i] == $iN - $iR + $i
        $i -= 1
    WEnd
    
    $aIdx[$i] += 1
    For $j = $i + 1 To $iR - 1
        $aIdx[$j] = $aIdx[$i] + $j - $i
    Next
    
    $iLeft -= 1
EndFunc

Exeter:

expandcollapse popup

#include-once
; #FUNCTION#;=========================================================================================

=====
; Name...........:  _ExeterPermute
; Description ...:  Returns an Array of the Permutations of all Elements in an Array
; Syntax.........:  _ExeterPermute(ByRef $avArray[, $sDelim = ""])
; Parameters ....:  $avArray        - The Array to get Permutations
;                   $sDelim         - [optional] String result separator, default is "" for none
; Return values .:  Success - Returns an Array of Permutations
;                     Returns an array, the first element ($array[0]) contains the number of strings returned.
;                     The remaining elements ($array[1], $array[2], etc.) contain the Permutations.
;                     Failure - Returns 0 and Sets @error:
;                     1 - The Input Must be an Array
; Author ........:  Erik Pilsits
; Modified.......:  07/08/2008
; Remarks .......:  The input array must be 0-based, ie no counter in $array[0]
;                   Based on an algorithm from Exeter University.
; Related .......:  _BogomolnyPermute.au3
; Link ..........:  http://www.bearcave.com/random_hacks/permute.html
;
; Example .......:  _ExeterPermute($array)
;
; ====================================================================================================


======
Func _ExeterPermute(ByRef $avArray, $sDelim = "")
    Local $i, $iSize = UBound($avArray), $iFactorial = 1, $aIdx[$iSize], $aResult[1], $iCount = 1
    
    If Not IsArray($avArray) Then
        Return SetError(1, 0, 0)
    EndIf
    
    For $i = 0 To $iSize - 1
        $aIdx[$i] = $i
    Next
    For $i = $iSize To 1 Step -1
        $iFactorial *= $i
    Next
    ReDim $aResult[$iFactorial + 1]
    $aResult[0] = $iFactorial
    _ExeterInternal($avArray, 0, $iSize, $sDelim, $aIdx, $aResult, $iCount)
    Return $aResult
EndFunc

Func _ExeterInternal(ByRef $avArray, $iStart, $iSize, $sDelim, ByRef $aIdx, ByRef $aResult, ByRef $iCount)
    Local $i, $sTemp = "", $iTemp
    
    If $iStart == $iSize - 1 Then
        For $i = 0 To $iSize - 1
            $aResult[$iCount] &= $avArray[$aIdx[$i]] & $sDelim
        Next
        If $sDelim <> "" Then $aResult[$iCount] = StringTrimRight($aResult[$iCount], 1)
        $iCount += 1
    Else
        For $i = $iStart To $iSize - 1
            $iTemp = $aIdx[$i]
            
            $aIdx[$i] = $aIdx[$iStart]
            $aIdx[$iStart] = $iTemp
            _ExeterInternal($avArray, $iStart + 1, $iSize, $sDelim, $aIdx, $aResult, $iCount)
            $aIdx[$iStart] = $aIdx[$i]
            $aIdx[$i] = $iTemp
        Next
    EndIf
EndFunc

Bogomolny:

expandcollapse popup

#include-once
; #FUNCTION#;=========================================================================================

=====
; Name...........:  _BogomolnyPermute
; Description ...:  Returns an Array of the Permutations of all Elements in an Array
; Syntax.........:  _BogomolnyPermute(ByRef $avArray[, $sDelim = ""])
; Parameters ....:  $avArray        - The Array to get Permutations
;                   $sDelim         - [optional] String result separator, default is "" for none
; Return values .:  Success - Returns an Array of Permutations
;                     Returns an array, the first element ($array[0]) contains the number of strings returned.
;                     The remaining elements ($array[1], $array[2], etc.) contain the Permutations.
;                     Failure - Returns 0 and Sets @error:
;                     1 - The Input Must be an Array
; Author ........:  Erik Pilsits
; Modified.......:  07/08/2008
; Remarks .......:  The input array must be 0-based, ie no counter in $array[0].
;                   Based on the algorithm by Alexander Bogomolny.
; Related .......:  _ExeterPermute.au3
; Link ..........:  http://www.bearcave.com/random_hacks/permute.html
;
; Example .......:  _BogomolnyPermute($array)
;
; ====================================================================================================


======
Func _BogomolnyPermute(ByRef $avArray, $sDelim = "")
    Local $i, $iSize = UBound($avArray), $iFactorial = 1, $aIdx[$iSize], $aResult[1], $iLevel = -1, $iCount = 1
    
    If Not IsArray($avArray) Then
        Return SetError(1, 0, 0)
    EndIf
    
    For $i = 0 To $iSize - 1
        $aIdx[$i] = 0
    Next
    For $i = $iSize To 1 Step -1
        $iFactorial *= $i
    Next
    ReDim $aResult[$iFactorial + 1]
    $aResult[0] = $iFactorial
    _BogomolnyInternal($avArray, 0, $iSize, $sDelim, $aIdx, $aResult, $iLevel, $iCount)
    Return $aResult
EndFunc

Func _BogomolnyInternal(ByRef $avArray, $iStart, $iSize, $sDelim, ByRef $aIdx, ByRef $aResult, ByRef $iLevel, ByRef $iCount)
    Local $i, $sTemp = ""
    
    $iLevel += 1
    $aIdx[$iStart] = $iLevel
    
    If $iLevel == $iSize Then
        For $i = 0 To $iSize - 1
            $aResult[$iCount] &= $avArray[$aIdx[$i] - 1] & $sDelim
        Next
        If $sDelim <> "" Then $aResult[$iCount] = StringTrimRight($aResult[$iCount], 1)
        $iCount += 1
    Else
        For $i = 0 To $iSize - 1
            If $aIdx[$i] == 0 Then
                _BogomolnyInternal($avArray, $i, $iSize, $sDelim, $aIdx, $aResult, $iLevel, $iCount)
            EndIf
        Next
    EndIf
    $iLevel -= 1
    $aIdx[$iStart] = 0
EndFunc

Speed Test Results - unsorted 7 and 8 element arrays:

7 elements:
Exeter: 0.469462180249166  sec
Bogomolny: 0.808011423239546  sec

8 elements:
Exeter: 3.88975994155682  sec
Bogomolny: 6.84402256432033  sec

I mean that's 32 times faster again than the new ones!!

I implemented this in a FreeBASIC DLL, just to learn FB. The actual permutation calculation for an 8 element array takes only 0.25380069254612 seconds, and it only takes about an additional 1 second to put the data into the AU3 array, for a total of 1.29078674803641 seconds. Ironically it takes like another 10 seconds just to display the array muttley

Edited July 16, 2008 by wraithdu

[litlmike]

Glad you like it! I hate to do this to you then, but while I was doing some other stuff, I decided to make a small adjustment and see what difference it made. I got rid of the _ArrayAdd() in all the functions. It turns out all the ReDims from the _ArrayAdd() is a HUGE performance hit. Here's the new funcs and speed test results -

Ironically it takes like another 10 seconds just to display the array muttley

Excellent! Thanks for the adjustments, it is nice to have someone else working on this, since my abilities are limited. That is a pretty nice bump in performance and we all will appreciate it. Funny, that it takes forever to display the array. I will repackage the files and post in the original post.

[GaryFrost]

Wow nice! What you have here is really great. Sorry I didn't respond sooner, I am supposed to get email notices when a post is made, but it looks it missed yours. Anyways, I took what you made and packaged it for the Au3 install set. Hopefully GaryFrost will include it. Funny to see that you posted that link, I also went there but didn't know how to convert the syntax. Thanks for all of this. Double check my notations to make sure I understood it all correctly.

Thanks!

I'm going to give the Array stuff more time, see if anymore changes. Seems like every time we think the array functions are good to go there are more changes.

There's no rush on these.

[litlmike]

I'm going to give the Array stuff more time, see if anymore changes. Seems like every time we think the array functions are good to go there are more changes.

There's no rush on these.

Fair enough, thanks for the update.

[wraithdu]

Here's another variation. This returns permutations of a set of items of a given length including duplicates; each return is of length n from a set of k items where each n can be any of k. The example is similar to binary counting to illustrate the output.

_DuplicatePermute()

expandcollapse popup

#include-once
; #FUNCTION#;=========================================================================================

=====
; Name...........:  _DuplicatePermute
; Description ...:  Returns an Array of Permutations (incl Duplicates) of a Given Length from Items in
;                   an Array
; Syntax.........:  _DuplicatePermute(ByRef $aArray, $iLen[, $sDelim = ""])
; Parameters ....:  $aArray         - The Array to get Permutations
;                   $iLen           - Length of each Permutation
;                   $sDelim         - [optional] String result separator, default is "" for none
; Return values .:  Success - Returns an Array of Permutations (incl Duplicates)
;                     Returns an array, the first element ($array[0]) contains the number of strings returned.
;                     The remaining elements ($array[1], $array[2], etc.) contain the Permutations.
;                     Failure - Returns 0 and Sets @error:
;                     1 - The Input Must be an Array
; Author ........:  Erik Pilsits
; Modified.......:  07/08/2008
; 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 .......:  _DuplicatePermute($array, 4)
;
; ====================================================================================================


======

Func _DuplicatePermute(ByRef $aArray, Const $iLen, $sDelim = "")
    If Not IsArray($aArray) Then
        Return SetError(1, 0, 0)
    EndIf
    
    Local Const $n = UBound($aArray)
    Local $avSlots[$iLen], $i, $avResult[1], $count
    
    $count = $n ^ $iLen
    Dim $avResult[$count + 1]
    $avResult[0] = $count
    $count = 1
    For $i = 0 To $iLen - 1
        $avSlots[$i] = 0
    Next
    While _DuplicateInternal($aArray, $avSlots, $iLen, $n, $sDelim, $avResult, $count)
    WEnd
    Return $avResult
EndFunc

Func _DuplicateInternal(ByRef $aArray, ByRef $avSlots, Const ByRef $iLen, Const ByRef $n, ByRef $sDelim, ByRef $avResult, ByRef $count)
    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)
    $avResult[$count] = $str
    $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

Example:

#include <Array.au3>

Dim $aInput[2] = [0, 1]
$aOut = _DuplicatePermute($aInput, 4)
_ArrayDisplay($aOut)

Edited July 30, 2008 by wraithdu

[litlmike]

Here's another variation. This returns permutations of a set of items of a given length including duplicates; each return is of length n from a set of k items where each n can be any of k. The example is similar to binary counting to illustrate the output.

_DuplicatePermute()

Thanks again. Can you give me a scenario when a user might use this? For official inclusion, it has to be a Func that will be commonly used.

[litlmike]

From GaryFrost:

If there are no changes needed, the Array.zip will be included into the Beta version. Thanks.

[wraithdu]

It's a variation on a theme really. Where will people use any of these on a regular basis? Anyway, I used it on a recent password brute forcer app for TrueCrypt (some forum people were forgetting parts of passwords, it automates the GUI so is slow as hell, but it works). This one guy knew his password, but forgot the capitalization. So I used this routine to create an array of 0 / 1 patterns where 0 was lowercase and 1 was uppercase.