litlmike Posted June 25, 2008 Share Posted June 25, 2008 (edited) 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/2009Made Improvements to _ArrayCombinationsInternal() based upon suggestions from bchris01New .Zip File for Download08/05/2008Fixed a typo07/16/2008Removed 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/2008Based upon the feedback of wraithdu: re-worked _ArrayPermute and added _ArrayCombinations. Download below.06/26/2008Added the ability to select an Array Range, and an example06/24/2008UDF with Examples:Downloaded 122 timesDownload:Array.zip Edited January 23, 2009 by litlmike _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
TehWhale Posted June 25, 2008 Share Posted June 25, 2008 This deserve to be in Array.au3 included in the AutoIt v3 Install set. Link to comment Share on other sites More sharing options...
litlmike Posted June 25, 2008 Author Share Posted June 25, 2008 This deserve to be in Array.au3 included in the AutoIt v3 Install set.Thanks, I really appreciate that. _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
jvanegmond Posted June 25, 2008 Share Posted June 25, 2008 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=43763http://www.autoitscript.com/forum/index.ph...mp;#entry325332 github.com/jvanegmond Link to comment Share on other sites More sharing options...
ptrex Posted June 25, 2008 Share Posted June 25, 2008 @litlmike Very Nice !! Regards, ptrex Contributions :Firewall Log Analyzer for XP - Creating COM objects without a need of DLL's - UPnP support in AU3Crystal Reports Viewer - PDFCreator in AutoIT - Duplicate File FinderSQLite3 Database functionality - USB Monitoring - Reading Excel using SQLRun Au3 as a Windows Service - File Monitor - Embedded Flash PlayerDynamic Functions - Control Panel Applets - Digital Signing Code - Excel Grid In AutoIT - Constants for Special Folders in WindowsRead data from Any Windows Edit Control - SOAP and Web Services in AutoIT - Barcode Printing Using PS - AU3 on LightTD WebserverMS LogParser SQL Engine in AutoIT - ImageMagick Image Processing - Converter @ Dec - Hex - Bin -Email Address Encoder - MSI Editor - SNMP - MIB ProtocolFinancial Functions UDF - Set ACL Permissions - Syntax HighLighter for AU3ADOR.RecordSet approach - Real OCR - HTTP Disk - PDF Reader Personal Worldclock - MS Indexing Engine - Printing ControlsGuiListView - Navigation (break the 4000 Limit barrier) - Registration Free COM DLL Distribution - Update - WinRM SMART Analysis - COM Object Browser - Excel PivotTable Object - VLC Media Player - Windows LogOnOff Gui -Extract Data from Outlook to Word & Excel - Analyze Event ID 4226 - DotNet Compiler Wrapper - Powershell_COM - New Link to comment Share on other sites More sharing options...
litlmike Posted June 26, 2008 Author Share Posted June 26, 2008 Thanks to everyone for the positive feedback. Are there any changes that should be made? _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
litlmike Posted June 26, 2008 Author Share Posted June 26, 2008 Added the ability to select an Array Range, and an example _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
litlmike Posted July 7, 2008 Author Share Posted July 7, 2008 Anyone have any criticism for this UDF, positive or negative? _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
wraithdu Posted July 7, 2008 Share Posted July 7, 2008 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. Link to comment Share on other sites More sharing options...
wraithdu Posted July 8, 2008 Share Posted July 8, 2008 (edited) 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 Link to comment Share on other sites More sharing options...
wraithdu Posted July 8, 2008 Share Posted July 8, 2008 (edited) 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%#Þ®kjب `¢¸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 Link to comment Share on other sites More sharing options...
litlmike Posted July 15, 2008 Author Share Posted July 15, 2008 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! _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
wraithdu Posted July 16, 2008 Share Posted July 16, 2008 (edited) 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 Link to comment Share on other sites More sharing options...
litlmike Posted July 16, 2008 Author Share Posted July 16, 2008 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 muttleyExcellent! 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. _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
GaryFrost Posted July 16, 2008 Share Posted July 16, 2008 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. Link to comment Share on other sites More sharing options...
litlmike Posted July 16, 2008 Author Share Posted July 16, 2008 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. _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
wraithdu Posted July 30, 2008 Share Posted July 30, 2008 (edited) 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 Link to comment Share on other sites More sharing options...
litlmike Posted August 5, 2008 Author Share Posted August 5, 2008 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. _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
litlmike Posted August 5, 2008 Author Share Posted August 5, 2008 From GaryFrost: If there are no changes needed, the Array.zip will be included into the Beta version. Thanks. _ArrayPermute()_ArrayUnique()Excel.au3 UDF Link to comment Share on other sites More sharing options...
wraithdu Posted August 5, 2008 Share Posted August 5, 2008 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. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now