Sign in to follow this  
Followers 0

_ArrayPermute() UDF

25 posts in this topic

Posted (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/2009

Made Improvements to _ArrayCombinationsInternal() based upon suggestions from bchris01

New .Zip File for Download

08/05/2008

Fixed a typo

07/16/2008

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

07/15/2008

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

06/26/2008

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

06/24/2008

UDF with Examples:

Downloaded 122 times

Download:

Array.zip

Edited by litlmike

Share this post


Link to post
Share on other sites



Posted

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

Share this post


Link to post
Share on other sites

Posted

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

Thanks, I really appreciate that.

Share this post


Link to post
Share on other sites

Posted

@litlmike

Very Nice !! :)

Regards,

ptrex

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

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

#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 by wraithdu

Share this post


Link to post
Share on other sites

Posted (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:

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

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

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

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

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

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

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

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

Exeter: 16.0039109020839 sec

Bogomolny: 16.35302259086 sec

devnull: 128.295503129588 sec

Exeter: 16.0464103677981 sec

Bogomolny: 16.3414037258925 sec

devnull: 128.545797231212 sec

Edited by wraithdu

Share this post


Link to post
Share on other sites

Posted

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!

Share this post


Link to post
Share on other sites

Posted (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:

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

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

#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 by wraithdu

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

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

#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 by wraithdu

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

From GaryFrost:

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

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

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 account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0