Jump to content

This site uses cookies. By continuing to browse the site you are agreeing to our use of cookies. Find out more here. X
X


Photo

_ArrayPermute() UDF


  • Please log in to reply
24 replies to this topic

#1 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 25 June 2008 - 12:02 AM

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:
Attached File  Array.zip   4.6KB   154 downloads

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








#2 TehWhale

TehWhale

    Whalee..

  • Banned (NOT IN USE)
  • 1,482 posts

Posted 25 June 2008 - 02:13 AM

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

#3 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 25 June 2008 - 02:51 PM

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

Thanks, I really appreciate that.

#4 Manadar

Manadar

         

  • MVPs
  • 10,833 posts

Posted 25 June 2008 - 02:56 PM

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

#5 ptrex

ptrex

    Universalist

  • MVPs
  • 2,413 posts

Posted 25 June 2008 - 03:59 PM

@litlmike

Very Nice !! :)

Regards,

ptrex

#6 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 26 June 2008 - 03:31 PM

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

#7 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 26 June 2008 - 04:37 PM

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

#8 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 07 July 2008 - 03:33 PM

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

#9 wraithdu

wraithdu

    this noise inside my head

  • MVPs
  • 2,405 posts

Posted 07 July 2008 - 11:07 PM

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.

#10 wraithdu

wraithdu

    this noise inside my head

  • MVPs
  • 2,405 posts

Posted 08 July 2008 - 04:53 AM

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


#11 wraithdu

wraithdu

    this noise inside my head

  • MVPs
  • 2,405 posts

Posted 08 July 2008 - 03:57 PM

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:

AutoIt         
#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[™H H™]›œÈ [™Ù]Èœ›ÜŽ‚ŽÈLH HH[œ]]Ý™H[ˆœ˜^BŽÈ]]܈ ‹‹‹‹‹‹‹ŽˆQšZÈ[Ú]ŽÈ[ÙYšYY ‹‹‹‹‹‹ŽˆL ËÌ ̌ ŽÈ™[XšÜÈ ‹‹‹‹‹‹Ž‚UH[œ]œ˜^H]Ý™H X˜ÙY YH›ÈÛÝ[ˆ[ˆ   ˆÌ ͎؜˜^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Ú^™H H B‚BIˆÌ ͎ØRYÉˆÌ ÍŽÚWHH  ˆÌ ͎ÚB‚S™^‚WÑ^]’[›˜[     ˆÌ ͎Ø]œ˜^K     ˆÌ ͎ÚTÚ^™K ˆÌ ͎ÜÑ[[K ˆÌ ͎ØRY     ˆÌ ͎ØT™Ý[ B‚IˆÌ ͎ØT™Ý[ÌHHP›Ý[™     ˆÌ ͎ØT™Ý[ H H 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Ú^™H H H[‚‚BQ›Üˆ  ˆÌ ͎ÚHH È    ˆÌ ͎ÚTÚ^™H H B‚BBIˆÌ ͎ÜÕ[ ˜[ÏH ˆÌ ͎Ø]œ˜^VÉˆÌ ÍŽØRYÉˆÌ ÍŽÚWWH   ˜[È  ˆÌ ͎ÜÑ[[B‚BS™^‚BRYˆ  ˆÌ ͎ÜÑ[[H  ›əÝÈ   œ][Ýɜ][ÝÈ[ˆ    ˆÌ ͎ÜÕ[HÝš[™Õš[TšYÚ     ˆÌ ͎ÜÕ[  JB‚BW̘^PY     ˆÌ ͎ØT™Ý[     ˆÌ ͎ÜÕ[ B‚Q[ÙB‚BQ›Üˆ ˆÌ ͎ÚHH  ˆÌ ͎ÚTݝȠ ˆÌ ͎ÚTÚ^™H H 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.


#12 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 15 July 2008 - 09:16 PM

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!

#13 wraithdu

wraithdu

    this noise inside my head

  • MVPs
  • 2,405 posts

Posted 16 July 2008 - 04:08 AM

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         
#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         
#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         
#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 :muttley:

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


#14 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 16 July 2008 - 03:21 PM

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.

#15 GaryFrost

GaryFrost

    I don't need your attitude. I have one of my own

  • Developers
  • 7,854 posts

Posted 16 July 2008 - 08:05 PM

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.

SciTE for AutoItDirections for Submitting Standard UDFs

Don't argue with an idiot; people watching may not be able to tell the difference.


#16 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 16 July 2008 - 08:13 PM

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.

#17 wraithdu

wraithdu

    this noise inside my head

  • MVPs
  • 2,405 posts

Posted 30 July 2008 - 10:06 PM

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


#18 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 05 August 2008 - 04:13 PM

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.

#19 litlmike

litlmike

    Struggling Learner

  • Active Members
  • PipPipPipPipPipPip
  • 688 posts

Posted 05 August 2008 - 04:14 PM

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

#20 wraithdu

wraithdu

    this noise inside my head

  • MVPs
  • 2,405 posts

Posted 05 August 2008 - 07:24 PM

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.




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users