24 replies to this topic

[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   4.6KB   127 downloads

Edited by litlmike, 23 January 2009 - 12:09 AM.

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

[Manadar]

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 -

AutoIt        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
EndFuncƒo݊÷ Ø   Ý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–öç2‚b33c¶Ɨ7BÂB ¤f÷"b33c¶’ÒFòb33c¶&W7VÇE³Ð ’b33c¶W&ÕFV×Òô'&•W&×WFR…7G&–æu7ƗB‚b33c¶&W7VÇE²b33c¶•ÒÂgV÷C·ÂgV÷C²Â2’ÂÂgV÷C²gV÷C²ÂÂgV÷C²gV÷C²ÂgV÷C²gV÷C² •ô'&”FVÆWFR‚b33c¶W&ÕFVא •ô'&”6öæ6FVæFR‚b33c¶W&ÒÂb33c¶W&ÕFVא¤æW‡@¢b33c¶W&ÕFV×Ò¢b33c¶W&Õ³ÒÒT&÷VæB‚b33c¶W&ҒÒ¥ô'&•6÷'B‚b33c¶W&Ґ¥ô'&”F—7Æ’‚b33c¶W&Ґ

Edited by wraithdu, 08 July 2008 - 05:05 AM.

[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 Too bad I can't take credit for the math

Combinations UDF:

AutoIt        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 ..........:  <a href='http://www.merriampark.com/comb.htm' class='bbc_url' title='External link' rel='nofollow external'>http://www.merriampark.com/comb.htm</a>
;
; 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
EndFuncƒo݊÷ ØL^µêÏz¹®µ«b¢p%‚Šâ¶šºÚ"µÍˆÚ[˜ÛYK[ۘÙBˆÚ[˜ÛYH ›̘^K˜]LəÝŽÈѕSÕSӈÈÏOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOBŽÈ˜[YK‹‹‹‹‹‹‹‹‹‹ŽˆWÑ^]”›]]BŽÈØܚ[ۈ‹‹ŽˆT™]›œÈ[ˆœ˜^HوH›]]][ۜÈو[[[Y[È[ˆ[ˆœ˜^BŽÈÞ[^‹‹‹‹‹‹‹‹ŽˆWÑ^]”›]]JžT™Yˆ   ˆÌ͎Ø]œ˜^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›]]][ۜ˂ŽÈQ˜Z[™HH™]›œÈ[™Ù]Èœ›ÜŽ‚ŽÈLHHH[œ]]Ý™H[ˆœ˜^BŽÈ]]܈‹‹‹‹‹‹‹ŽˆQšZÈ[Ú]ŽÈ[ÙYšYY‹‹‹‹‹‹ŽˆL
ËÌ̌ŽÈ™[XšÜÈ‹‹‹‹‹‹Ž‚UH[œ]œ˜^H]Ý™HX˜ÙYYH›ÈÛÝ[ˆ[ˆ   ˆÌ͎؜˜^VÌBŽÂBBBBP˜ÙYۈ[ˆ[Ûܚ]Hœ›ÛH^]ˆ[š]™œÚ]K‚ŽÈ™[]Y‹‹‹‹‹‹Ž‚WЛÙÛÛ[ÛžT›]]K˜]LŽÈ[šÈ‹‹‹‹‹‹‹‹‹Ž‚Z‹ËÝÝݢ™X˜Ø]™K˜ÛÛKܘ[™ÛWÚXÚÜËÜ›]]Kš[ŽÂŽÈ^[H‹‹‹‹‹‹Ž‚WÑ^]”›]]J   ˆÌ͎؜˜^JBŽÂŽÈOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOB‘[˜ÈÑ^]”›]]JžT™Yˆ ˆÌ͎Ø]œ˜^K   ˆÌ͎ÜÑ[[HH    œ][Ýɜ][ÝÊB‚SØØ[   ˆÌ͎ÚK   ˆÌ͎ÚTÚ^™HHP›Ý[™
    ˆÌ͎Ø]œ˜^JK  ˆÌ͎ØRYɈÌ͎ÚTÚ^™WK   ˆÌ͎ØT™Ý[ÌWB‚B‚RYˆ›Ý̘^J ˆÌ͎Ø]œ˜^JH[‚‚BT™]›ˆÙ]œ›ÜŠK
B‚Q[™Y‚‚B‚Q›Üˆ ˆÌ͎ÚHHÈ    ˆÌ͎ÚTÚ^™HHB‚BIˆÌ͎ØRYɈÌ͎ÚWHH  ˆÌ͎ÚB‚S™^‚WÑ^]’[›˜[
    ˆÌ͎Ø]œ˜^K    ˆÌ͎ÚTÚ^™K ˆÌ͎ÜÑ[[K ˆÌ͎ØRY    ˆÌ͎ØT™Ý[
B‚IˆÌ͎ØT™Ý[ÌHHP›Ý[™
    ˆÌ͎ØT™Ý[
HHB‚T™]›ˆ    ˆÌ͎ØT™Ý[‘[™[˜Â‚‘[˜ÈÑ^]’[›˜[
žT™Yˆ   ˆÌ͎Ø]œ˜^K   ˆÌ͎ÚTݝ ˆÌ͎ÚTÚ^™K ˆÌ͎ÜÑ[[KžT™Yˆ    ˆÌ͎ØRYžT™Yˆ   ˆÌ͎ØT™Ý[
B‚SØØ[ ˆÌ͎ÚK   ˆÌ͎ÜÕ[H  œ][Ýɜ][ÝË ˆÌ͎ÚU[‚B‚RYˆ    ˆÌ͎ÚTݝOH   ˆÌ͎ÚTÚ^™HHH[‚‚BQ›Üˆ  ˆÌ͎ÚHHÈ    ˆÌ͎ÚTÚ^™HHB‚BBIˆÌ͎ÜÕ[ ˜[ÏH ˆÌ͎Ø]œ˜^VɈÌ͎ØRYɈÌ͎ÚWWH   ˜[È  ˆÌ͎ÜÑ[[B‚BS™^‚BRYˆ  ˆÌ͎ÜÑ[[H  ›əÝÈ   œ][Ýɜ][ÝÈ[ˆ    ˆÌ͎ÜÕ[HÝš[™Õš[TšYÚ
    ˆÌ͎ÜÕ[JB‚BW̘^PY
    ˆÌ͎ØT™Ý[    ˆÌ͎ÜÕ[
B‚Q[ÙB‚BQ›Üˆ ˆÌ͎ÚHH  ˆÌ͎ÚTݝȠ ˆÌ͎ÚTÚ^™HHB‚BBIˆÌ͎ÚU[H    ˆÌ͎ØRYɈÌ͎ÚWB‚BBB‚BBIˆÌ͎ØRYɈÌ͎ÚWHH    ˆÌ͎ØRYɈÌ͎ÚTݝB‚BBIˆÌ͎ØRYɈÌ͎ÚTݝHH ˆÌ͎ÚU[‚BBWÑ^]’[›˜[
    ˆÌ͎Ø]œ˜^K   ˆÌ͎ÚTݝ
ÈK   ˆÌ͎ÚTÚ^™K ˆÌ͎ÜÑ[[K ˆÌ͎ØRY    ˆÌ͎ØT™Ý[
B‚BBIˆÌ͎ØRYɈÌ͎ÚTݝHH    ˆÌ͎ØRYɈÌ͎ÚWB‚BBIˆÌ͎Ø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â'&’öbF†RW&×WFF–öç2öbÆÂVÆVÖVçG2–ââ'&£²7–çF‚ââââââââ㢕ô&övöÖöÆç•W&×WFR„'•&Vbb33c¶d'&•²Âb33c·4FVƖÒÒgV÷C²gV÷CµÒ£²&ÖWFW'2âââ㢒b33c¶d'&’ÒF†R'&’FòvWBW&×WFF–öç0£°’b33c·4FVƖА’Ò¶÷F–öæÅÒ7G&–ær&W7VÇB6W&F÷"ÂFVfVÇB—2gV÷C²gV÷C²f÷"æöæP£²&WGW&âfÇVW2㠕7V66W72Ò&WGW&ç2â'&’öbW&×WFF–öç0£²•&WGW&ç2â'&’ÂF†Rf—'7BVÆVÖVçB‚b33c¶'&•³Ғ6öçF–ç2F†RçVÖ&W"öb7G&–æw2&WGW&æVBࣲ•F†R&VÖ–æ–ærVÆVÖVçG2‚b33c¶'&•³ÒÂb33c¶'&•³%ÒÂWF2â’6öçF–âF†RW&×WFF–öç2ࣲ”f–ÇW&RÒ&WGW&ç2æB6WG2W'&÷# £²“ÒF†R–çWB×W7B&Râ'&£²WF†÷"âââââââ㢔W&–²–Ç6—G0£²ÖöF–f–VBââââââ㢓ró‚ó#€£²&VÖ&·2ââââââ㠕F†R–çWB'&’×W7B&RÖ&6VB–Ræò6÷VçFW"–âb33c¶'&•³Òࣰ”&6VBöâF†RÆv÷&—F†Ò'’ÆW†æFW"&övöÖöÆç’ࣲ&VÆFVBââââââ㠕ôW†WFW%W&×WFRæS0£²Ɩæ²âââââââââ㠖‡GG¢ò÷wwræ&V&6fRæ6öÒ÷&æFöÕö†6·2÷W&×WFRæ‡FÖÀ£°£²W†×ÆRââââââ㠕ô&övöÖöÆç•W&×WFR‚b33c¶'&’£°£²ÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓÓФgVæ2ô&övöÖöÆç•W&×WFR„'•&Vbb33c¶d'&’Âb33c·4FVƖÒÒgV÷C²gV÷C² ”Æö6Âb33c¶’Âb33c¶•6—¦RÒT&÷VæB‚b33c¶d'&’’Âb33c¶–G…²b33c¶•6—¦UÒÂb33c¶&W7VÇE³ÒÂb33c¶”ÆWfVÂÒÓ  ”–bæ÷B—4'&’‚b33c¶d'&’’F†Và •&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æB‚b33c¶&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—¦RF†Và ”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²F†Vâb33c·5FV×Ò7G&–æuG&–Õ&–v‡B‚b33c·5FVא •ô'&”FB‚b33c¶&W7VÇBÂb33c·5FVא ”VÇ6P ”f÷"b33c¶’ÒFòb33c¶•6—¦RÒ ”–bb33c¶–G…²b33c¶•ÒÓÒF†Và •ô&ö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µôW†WFW%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æB‚b33c¶'&’’Ò ’b33c¶'&•²b33c¶•ÒÒb33c¶’²¤æW‡@ ¢b33c·F–ÖW"ÒF–ÖW$–æ—B‚¢b33c¶&W7VÇBÒôW†WFW%W&×WFR‚b33c¶'&’¤6öç6öÆUw&—FR‚gV÷C´W†WFW#¢gV÷C²fײF–ÖW$F–fb‚b33c·F–ÖW"’òfײgV÷C²6V2gV÷C²fײ5$Äb¥ô'&”F—7Æ’‚b33c¶&W7VÇB ¢b33c·F–ÖW"ÒF–ÖW$–æ—B‚¢b33c¶&W7VÇBÒô&övöÖöÆç•W&×WFR‚b33c¶'&’¤6öç6öÆUw&—FR‚gV÷C´&övöÖöÆ瓢gV÷C²fײF–ÖW$F–fb‚b33c·F–ÖW"’òfײgV÷C²6V2gV÷C²fײ5$Äb¥ô'&”F—7Æ’‚b33c¶&W7VÇB ¢b33c·F–ÖW"ÒF–ÖW$–æ—B‚¢b33c¶&W7VÇBÒô'&•W&×WFR‚b33c¶'&’ÂÂgV÷C²gV÷C²ÂÂgV÷C²gV÷C²ÂgV÷C²gV÷C²¤6öç6öÆUw&—FR‚gV÷C¶FWfçVÆâgV÷C²fײF–ÖW$F–fb‚b33c·F–ÖW"’òfײgV÷C²6V2gV÷C²fײ5$Äb¥ô'&”F—7Æ’‚b33c¶&W7VÇBƒo݊÷ Ø[¥”÷«šë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 by wraithdu, 08 July 2008 - 03:59 PM.

[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 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:

Plain Text        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 ..........:  <a href='http://www.merriampark.com/comb.htm' class='bbc_url' title='External link' rel='nofollow external'>http://www.merriampark.com/comb.htm</a>
;
; 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:

Plain Text        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 ..........:  <a href='http://www.bearcave.com/random_hacks/permute.html' class='bbc_url' title='External link' rel='nofollow external'>http://www.bearcave.com/random_hacks/permute.html</a>
;
; 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:

Plain Text        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 ..........:  <a href='http://www.bearcave.com/random_hacks/permute.html' class='bbc_url' title='External link' rel='nofollow external'>http://www.bearcave.com/random_hacks/permute.html</a>
;
; 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

Edited by wraithdu, 16 July 2008 - 04:34 AM.

[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

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()

Plain Text        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 ..........:  <a href='http://higherlogics.blogspot.com/2008/04/permutations-with-duplicates-in-c.html' class='bbc_url' title='External link' rel='nofollow external'>http://higherlogics.blogspot.com/2008/04/permutations-with-duplicates-in-c.html</a>
;
; 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 by wraithdu, 30 July 2008 - 10:07 PM.

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