All permutations of a collections of bit flags.

[Zinthose]

Greetings,

I'm trying to determine all the possible permutations of a collection of bit flags so I have all the possible values that Altiris.

Currently I'm using a method to iterate through all int32 values performing a BitAnd looking for matches. This is very inefficient and also takes a long time. Anyone have any tips to speed up the process?

;## Determine all permutations of Bit Flags
#Include <Array.au3>

Global $BaseFlag = 512
Global $SuccessFlags = 0x4 + 0x10 + 0x2000 + 0x20000 + 0x40000

ConsoleWrite("! " & _Permutations($BaseFlag, $SuccessFlags) & @CRLF)

Func _Permutations ($BaseFlag, $SuccessFlags)
    Local $SuccessCodes = ""
    Local $TestNumber = 1
    Local $TestBit = 0
    Local $Pattern = ""
    
    ConsoleWrite("! Please Wait...  This can take a very long time to calculate all possible permutations." & @CRLF)
    
    While True
        $TestBit = BitAND($SuccessFlags, $TestNumber) + $BaseFlag
        $TestBit = BitOR($TestBit, $BaseFlag)
        
        If $TestBit <> 0 Then
            $Pattern = "(\A|,)" & String($TestBit) & "(\z|,)"
            If StringRegExp($SuccessCodes, $Pattern) = 0 Then 
                If $SuccessCodes <> "" Then $SuccessCodes &= ","
                $SuccessCodes &= String($TestBit)
            EndIf
        EndIf
        
        ;$TestBit = BitShift($TestBit, -1)
        If $TestNumber = 0x7FFFFFFF  Or $TestNumber >= $SuccessFlags Then ExitLoop; <== Added "Or $TestNumber >= $SuccessFlags" which will shorten the process time as long as no high value bit flag is in use or even the negative bit.
        $TestNumber += 1
    WEnd

    Return $SuccessCodes
EndFunc

Edited September 11, 2008 by Zinthose

[PsaltyDS]

Greetings,

I'm trying to determine all the possible permutations of a collection of bit flags so I have all the possible values that Altiris.

Currently I'm using a method to iterate through all int32 values performing a BitAnd looking for matches. This is very inefficient and also takes a long time. Anyone have any tips to speed up the process?

;## Determine all permutations of Bit Flags
#Include <Array.au3>

Global $BaseFlag = 512
Global $SuccessFlags = 0x4 + 0x10 + 0x2000 + 0x20000 + 0x40000

ConsoleWrite("! " & _Permutations($BaseFlag, $SuccessFlags) & @CRLF)

Func _Permutations ($BaseFlag, $SuccessFlags)
    Local $SuccessCodes = ""
    Local $TestNumber = 1
    Local $TestBit = 0
    Local $Pattern = ""
    
    ConsoleWrite("! Please Wait...  This can take a very long time to calculate all possible permutations." & @CRLF)
    
    While True
        $TestBit = BitAND($SuccessFlags, $TestNumber) + $BaseFlag
        $TestBit = BitOR($TestBit, $BaseFlag)
        
        If $TestBit <> 0 Then
            $Pattern = "(\A|,)" & String($TestBit) & "(\z|,)"
            If StringRegExp($SuccessCodes, $Pattern) = 0 Then 
                If $SuccessCodes <> "" Then $SuccessCodes &= ","
                $SuccessCodes &= String($TestBit)
            EndIf
        EndIf
        
    ;$TestBit = BitShift($TestBit, -1)
        If $TestNumber = 0x7FFFFFFF  Or $TestNumber >= $SuccessFlags Then ExitLoop; <== Added "Or $TestNumber >= $SuccessFlags" which will shorten the process time as long as no high value bit flag is in use or even the negative bit.
        $TestNumber += 1
    WEnd

    Return $SuccessCodes
EndFunc

You only need a bit per value to permutate (5 bits = 32 permutations = .003sec on my computer):

Global $BaseFlag = 512
Global $SuccessFlags[5] = [0x4, 0x10, 0x2000, 0x20000, 0x40000]
$Results = ""
$iTimer = TimerInit()
For $n = 0 To (2^5) - 1
    $Test = $BaseFlag
    For $b = 0 To 4
        If BitAND(2^$b, $n) Then $Test += $SuccessFlags[$b]
    Next
    $Results &= "0x" & Hex($Test,5) & @CRLF
Next
$Results = StringTrimRight($Results, 1)
$nTimer = Round(TimerDiff($iTimer)/1000, 3)
ConsoleWrite("$Results in " & $nTimer & "sec" & @LF & $Results & @LF)

[Zinthose]

You only need a bit per value to permutate (5 bits = 32 permutations = .003sec on my computer):

Global $BaseFlag = 512
Global $SuccessFlags[5] = [0x4, 0x10, 0x2000, 0x20000, 0x40000]
$Results = ""
$iTimer = TimerInit()
For $n = 0 To (2^5) - 1
    $Test = $BaseFlag
    For $b = 0 To 4
        If BitAND(2^$b, $n) Then $Test += $SuccessFlags[$b]
    Next
    $Results &= "0x" & Hex($Test,5) & @CRLF
Next
$Results = StringTrimRight($Results, 1)
$nTimer = Round(TimerDiff($iTimer)/1000, 3)
ConsoleWrite("$Results in " & $nTimer & "sec" & @LF & $Results & @LF)

>_<

Sweet! This is allot faster... now I just need to pick it apart to understand it.

[Malkey]

To enhance your example to make it more visual, added binary output.

Global $BaseFlag = 512
Global $SuccessFlags[5] = [0x4, 0x10, 0x2000, 0x20000, 0x40000]
$Results = ""
$iTimer = TimerInit()
For $n = 0 To (2 ^ 5) - 1
    $Test = $BaseFlag
    For $b = 0 To 4
        If BitAND(2 ^ $b, $n) Then $Test += $SuccessFlags[$b]
    Next
    $Results &= "0x" & Hex($Test, 5) & " = " & Hex2Bin("0x" & Hex($Test, 5)) & @CRLF
Next
;$Results = StringTrimRight($Results, 1)
$nTimer = Round(TimerDiff($iTimer) / 1000, 3)
ConsoleWrite("$Results in " & $nTimer & "sec" & @LF & $Results)

Func Hex2Bin($hex)
    Local $b = ""
    For $i = 1 To 32
        $b = BitAND($hex, 1) & $b
        $hex = BitShift($hex, 1)
    Next
    Return $b
EndFunc   ;==>Hex2Bin