combinations problem - (Moved)

[CFLam]

Hello all,

        I have a large set of numeric data (50,000 sets, in 2500 layers, each layer has 20 sets of data, range from 1 to 60), each set has 8 sequences, each sequence has at least 1 and at most 15 numbers e.g.:

[1,2,3,4,5,6,7,8]

[4,5,7,12,23,28,44,56,57]

[3,6,9]

[12,13,18,22,28,29,33,37,40,42,51,57]

[2,15,47,56]

[6,8,9,12,15,18,22,29,33,35]

[41,51,53,55,57,59]

[12,21,31,41,47,55,56,57,58,59]

 

I need to generate combinations of 8 numbers from the above sequences e.g.

1,4,3,12,2,6,41,12 and then check if the result contain duplicate number (for this case, 12 is duplicated) and discard this result, pseudo code below:

     for $a=0 to ubound(seq 1)-1
     for $b=0 to ubound(seq 2)-1
     for $c=0 to ubound(seq 3)-1
     for $d=0 to ubound(seq 4)-1
     for $e=0 to ubound(seq 5)-1
     for $f=0 to ubound(seq 6)-1
     for $g=0 to ubound(seq 7)-1
     for $h=0 to ubound(seq 8)-1
       $resArr[0]=$Seq1[$a]
       $resArr[1]=$Seq2[$b]
       $resArr[2]=$Seq3[$c]
       $resArr[3]=$Seq4[$d]
       $resArr[4]=$Seq5[$e]
       $resArr[5]=$Seq6[$f]
       $resArr[6]=$Seq7[$g]
       $resArr[7]=$Seq8[$h]
       $uniArr=_arrayunique($resArr)
        if $uniArr[0] = 8 then
         _arraysort($uniArr,0,1)
         $outStr=$uArr[1] & "," & $uniArr[2] & "," & $uniArr[3] & "," & $uniArr[4] & "," & $uniArr[5] & "," & $uniArr[6] & "," & $uniArr[7] & "," & $uniArr[8]
         filewriteline($outSelFileHdl,$outStr)

 

However, The above code take around 1.5 hours to handle 1 layer (i.e. 20 set of data). Does the above code can further optimize to shorten the execution time ? Or I need to use SQLite to do the job ? (i.e. create 8 tables or 8 sequences) and select * with the joined tables ? Will this faster ? Thanks.

 

Regds

CFLam

[Melba23]

Moved to the appropriate AutoIt General Help and Support forum, as the AutoIt Example Scripts forum very clearly states:

Quote

Share your cool AutoIt scripts, UDFs and applications with others.

---

Do not post general support questions here, instead use the AutoIt Help and Support forums.

Moderation Team

[Numeric1]

As you mentioned earlier, you could already improve performance by applying early filtering in your nested loops to avoid generating combinations that contain duplicates. This can significantly reduce the number of evaluated combinations, especially when the sequences are long.

But if you want to go even further in terms of performance, you might also consider a hybrid solution:
1°) Write a function in C++ (as a DLL) that handles the generation of valid combinations with uniqueness checks directly in a much faster language,
then
2°) Call that DLL from AutoIt using DllCall().

This way, you can keep your AutoIt interface while offloading the heavy computation to a more efficient backend.

[Nine]

Funny. I wonder why you post it in pseudo-code when you know that AutoIt is performing it in 1.5hr... Why didn't you use your own code instead ?!?

Anyway, I was able to reduce your 1.5hr into about 20 secs with Optimization and Multi-threading.  I tested with small amount of data and it seems to work fine.

Here :

expandcollapse popup

#include <Array.au3>
#include <FileConstants.au3>
#include "..\Files\PMT-UDF.AU3"

Local $a1 = [1, 2, 3, 4, 5, 6, 7, 8]
Local $a2 = [4, 5, 7, 12, 23, 28, 44, 56, 57]
$s2 = _ArrayToString($a2)
Local $a3 = [3, 6, 9]
$s3 = _ArrayToString($a3)
Local $a4 = [12, 13, 18, 22, 28, 29, 33, 37, 40, 42, 51, 57]
$s4 = _ArrayToString($a4)
Local $a5 = [2, 15, 47, 56]
$s5 = _ArrayToString($a5)
Local $a6 = [6, 8, 9, 12, 15, 18, 22, 29, 33, 35]
$s6 = _ArrayToString($a6)
Local $a7 = [41, 51, 53, 55, 57, 59]
$s7 = _ArrayToString($a7)
Local $a8 = [12, 21, 31, 41, 47, 55, 56, 57, 58, 59]
$s8 = _ArrayToString($a8)

_PMT_Init()

Local $aProcess[UBound($a1)]

For $i = 0 To UBound($a1) - 1
  $aProcess[$i] = _PMT_Start("Check", $a1[$i], $s2, $s3, $s4, $s5, $s6, $s7, $s8, "Files\" & $i & ".txt")
Next

While Sleep(100)
  For $i = 0 To UBound($aProcess) - 1
    If ProcessExists($aProcess[$i]) Then ContinueLoop 2
  Next
  ExitLoop
WEnd

# todo merge the 8 files with DOS command

Func Check($a1, $s2, $s3, $s4, $s5, $s6, $s7, $s8, $sFile)
  Local $a2 = StringSplit($s2, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a2) - 1
    $a2[$i] = Number($a2[$i])
  Next
  Local $a3 = StringSplit($s3, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a3) - 1
    $a3[$i] = Number($a3[$i])
  Next
  Local $a4 = StringSplit($s4, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a4) - 1
    $a4[$i] = Number($a4[$i])
  Next
  Local $a5 = StringSplit($s5, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a5) - 1
    $a5[$i] = Number($a5[$i])
  Next
  Local $a6 = StringSplit($s6, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a6) - 1
    $a6[$i] = Number($a6[$i])
  Next
  Local $a7 = StringSplit($s7, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a7) - 1
    $a7[$i] = Number($a7[$i])
  Next
  Local $a8 = StringSplit($s8, "|", $STR_NOCOUNT)
   For $i = 0 to UBound($a8) - 1
    $a8[$i] = Number($a8[$i])
  Next
  Local $hFile = FileOpen($sFile, $FO_OVERWRITE)
  Local $resArr[8] = [$a1], $outStr, $sorArr

  For $b = 0 To UBound($a2) - 1
    If $a2[$b] = $a1 Then ContinueLoop
    $resArr[1] = $a2[$b]
    For $c = 0 To UBound($a3) - 1
      If $a3[$c] = $a1 Or $a3[$c] = $a2[$b] Then ContinueLoop
      $resArr[2] = $a3[$c]
      For $d = 0 To UBound($a4) - 1
        If $a4[$d] = $a1 Or $a4[$d] = $a2[$b] Or $a4[$d] = $a3[$c] Then ContinueLoop
        $resArr[3] = $a4[$d]
        For $e = 0 To UBound($a5) - 1
          If $a5[$e] = $a1 Or $a5[$e] = $a2[$b] Or $a5[$e] = $a3[$c] Or $a5[$e] = $a4[$d] Then ContinueLoop
          $resArr[4] = $a5[$e]
          For $f = 0 To UBound($a6) - 1
            If $a6[$f] = $a1 Or $a6[$f] = $a2[$b] Or $a6[$f] = $a3[$c] Or $a6[$f] = $a4[$d] Or $a6[$f] = $a5[$e] Then ContinueLoop
            $resArr[5] = $a6[$f]
            For $g = 0 To UBound($a7) - 1
              If $a7[$g] = $a1 Or $a7[$g] = $a2[$b] Or $a7[$g] = $a3[$c] Or $a7[$g] = $a4[$d] Or $a7[$g] = $a5[$e] Or $a7[$g] = $a6[$f] Then ContinueLoop
              $resArr[6] = $a7[$g]
              For $h = 0 To UBound($a8) - 1
                If $a8[$h] = $a1 Or $a8[$h] = $a2[$b] Or $a8[$h] = $a3[$c] Or $a8[$h] = $a4[$d] Or $a8[$h] = $a5[$e] Or $a8[$h] = $a6[$f] Or $a8[$h] = $a7[$g] Then ContinueLoop
                $resArr[7] = $a8[$h]
                $sorArr = $resArr
                _ArraySort($sorArr)
                $outStr &= $sorArr[0] & "," & $sorArr[1] & "," & $sorArr[2] & "," & $sorArr[3] & "," & $sorArr[4] & "," & $sorArr[5] & "," & $sorArr[6] & "," & $sorArr[7] & @CRLF
              Next
            Next
          Next
        Next
      Next
    Next
    FileWrite($hFile, $outStr)
    $outStr = ""
  Next
  FileClose($hFile)
EndFunc   ;==>Check

You can find my multi-threading UDF in my signature.

ps.  I was able to reduce it to 12 secs but rewriting the _ArraySort to fit the situation (not included)...

Edited Wednesday at 11:55 PM by Nine

[UEZ]

I tested it in Freebasic and it took to generate the 6220800 combinations and ignoring duplicates values per line ~72 ms.

Non duplicate entries: 3219062

I agree with @Numeric1 to  outsource the code to a DLL.

[UEZ]

I created a DLL (x64) to do the job:

;coded by UEZ build 2025-06-12
#AutoIt3Wrapper_UseX64=y
#include <Array.au3>

Local $a1 = [1, 2, 3, 4, 5, 6, 7, 8]
Local $a2 = [4, 5, 7, 12, 23, 28, 44, 56, 57]
Local $a3 = [3, 6, 9]
Local $a4 = [12, 13, 18, 22, 28, 29, 33, 37, 40, 42, 51, 57]
Local $a5 = [2, 15, 47, 56]
Local $a6 = [6, 8, 9, 12, 15, 18, 22, 29, 33, 35]
Local $a7 = [41, 51, 53, 55, 57, 59]
Local $a8 = [12, 21, 31, 41, 47, 55, 56, 57, 58, 59]

Local $aAll = [$a1, $a2, $a3, $a4, $a5, $a6, $a7, $a8]

Generate($aAll)

Func Generate($aArrayOfArrays, $sOutput = @ScriptDir & "\array_output.txt")
    Local $tagDLL, $i, $j
    For $i = 0 To UBound($aArrayOfArrays) - 1
        $tagDLL &= "ubyte a" & $i & "[" & UBound($aArrayOfArrays[$i]) & "];"
    Next
    Local $tArrays = DllStructCreate($tagDLL), $a, $tUBArrays = DllStructCreate("ubyte ub[8]")
    For $i = 0 To UBound($aArrayOfArrays) - 1
        $a = $aArrayOfArrays[$i]
        For $j = 0 To UBound($a) - 1
            DllStructSetData($tArrays, $i + 1, $a[$j], $j + 1)
        Next
        $tUBArrays.ub(($i + 1)) = UBound($a) - 1
    Next
    Local $t = TimerInit()
    Local $iResult = DllCall("DoTheJobForMe.dll", "uint", "GenerateCombinations", "struct*", $tArrays, "ushort", DllStructGetSize($tArrays), "struct*", $tUBArrays, "str", $sOutput)[0]
    ConsoleWrite(TimerDiff($t) & " ms" & @CRLF)
    ConsoleWrite("Wrote " & $iResult & " lines to file " & $sOutput & @CRLF)
EndFunc

DLL: DoTheJobForMe-DLL.7z

Put the DLL to script dir.

 

How long does it take?

 

Btw, what is the purpose for all these combinations?

Edited Thursday at 01:13 PM by UEZ

[CFLam]

On 6/12/2025 at 2:16 AM, Numeric1 said:

As you mentioned earlier, you could already improve performance by applying early filtering in your nested loops to avoid generating combinations that contain duplicates. This can significantly reduce the number of evaluated combinations, especially when the sequences are long.

But if you want to go even further in terms of performance, you might also consider a hybrid solution:
1°) Write a function in C++ (as a DLL) that handles the generation of valid combinations with uniqueness checks directly in a much faster language,
then
2°) Call that DLL from AutoIt using DllCall().

This way, you can keep your AutoIt interface while offloading the heavy computation to a more efficient backend.

Thanks for your reply. Eventually I resolve the issue by handle ArrayUnique myself (instead of calling the function) and use Scripting.dictionary to de-duplicate the list. Performance improve a lot.

[CFLam]

On 6/12/2025 at 4:05 AM, Nine said:

Funny. I wonder why you post it in pseudo-code when you know that AutoIt is performing it in 1.5hr... Why didn't you use your own code instead ?!?

Anyway, I was able to reduce your 1.5hr into about 20 secs with Optimization and Multi-threading.  I tested with small amount of data and it seems to work fine.

Here :

expandcollapse popup

#include <Array.au3>
#include <FileConstants.au3>
#include "..\Files\PMT-UDF.AU3"

Local $a1 = [1, 2, 3, 4, 5, 6, 7, 8]
Local $a2 = [4, 5, 7, 12, 23, 28, 44, 56, 57]
$s2 = _ArrayToString($a2)
Local $a3 = [3, 6, 9]
$s3 = _ArrayToString($a3)
Local $a4 = [12, 13, 18, 22, 28, 29, 33, 37, 40, 42, 51, 57]
$s4 = _ArrayToString($a4)
Local $a5 = [2, 15, 47, 56]
$s5 = _ArrayToString($a5)
Local $a6 = [6, 8, 9, 12, 15, 18, 22, 29, 33, 35]
$s6 = _ArrayToString($a6)
Local $a7 = [41, 51, 53, 55, 57, 59]
$s7 = _ArrayToString($a7)
Local $a8 = [12, 21, 31, 41, 47, 55, 56, 57, 58, 59]
$s8 = _ArrayToString($a8)

_PMT_Init()

Local $aProcess[UBound($a1)]

For $i = 0 To UBound($a1) - 1
  $aProcess[$i] = _PMT_Start("Check", $a1[$i], $s2, $s3, $s4, $s5, $s6, $s7, $s8, "Files\" & $i & ".txt")
Next

While Sleep(100)
  For $i = 0 To UBound($aProcess) - 1
    If ProcessExists($aProcess[$i]) Then ContinueLoop 2
  Next
  ExitLoop
WEnd

# todo merge the 8 files with DOS command

Func Check($a1, $s2, $s3, $s4, $s5, $s6, $s7, $s8, $sFile)
  Local $a2 = StringSplit($s2, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a2) - 1
    $a2[$i] = Number($a2[$i])
  Next
  Local $a3 = StringSplit($s3, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a3) - 1
    $a3[$i] = Number($a3[$i])
  Next
  Local $a4 = StringSplit($s4, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a4) - 1
    $a4[$i] = Number($a4[$i])
  Next
  Local $a5 = StringSplit($s5, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a5) - 1
    $a5[$i] = Number($a5[$i])
  Next
  Local $a6 = StringSplit($s6, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a6) - 1
    $a6[$i] = Number($a6[$i])
  Next
  Local $a7 = StringSplit($s7, "|", $STR_NOCOUNT)
  For $i = 0 to UBound($a7) - 1
    $a7[$i] = Number($a7[$i])
  Next
  Local $a8 = StringSplit($s8, "|", $STR_NOCOUNT)
   For $i = 0 to UBound($a8) - 1
    $a8[$i] = Number($a8[$i])
  Next
  Local $hFile = FileOpen($sFile, $FO_OVERWRITE)
  Local $resArr[8] = [$a1], $outStr, $sorArr

  For $b = 0 To UBound($a2) - 1
    If $a2[$b] = $a1 Then ContinueLoop
    $resArr[1] = $a2[$b]
    For $c = 0 To UBound($a3) - 1
      If $a3[$c] = $a1 Or $a3[$c] = $a2[$b] Then ContinueLoop
      $resArr[2] = $a3[$c]
      For $d = 0 To UBound($a4) - 1
        If $a4[$d] = $a1 Or $a4[$d] = $a2[$b] Or $a4[$d] = $a3[$c] Then ContinueLoop
        $resArr[3] = $a4[$d]
        For $e = 0 To UBound($a5) - 1
          If $a5[$e] = $a1 Or $a5[$e] = $a2[$b] Or $a5[$e] = $a3[$c] Or $a5[$e] = $a4[$d] Then ContinueLoop
          $resArr[4] = $a5[$e]
          For $f = 0 To UBound($a6) - 1
            If $a6[$f] = $a1 Or $a6[$f] = $a2[$b] Or $a6[$f] = $a3[$c] Or $a6[$f] = $a4[$d] Or $a6[$f] = $a5[$e] Then ContinueLoop
            $resArr[5] = $a6[$f]
            For $g = 0 To UBound($a7) - 1
              If $a7[$g] = $a1 Or $a7[$g] = $a2[$b] Or $a7[$g] = $a3[$c] Or $a7[$g] = $a4[$d] Or $a7[$g] = $a5[$e] Or $a7[$g] = $a6[$f] Then ContinueLoop
              $resArr[6] = $a7[$g]
              For $h = 0 To UBound($a8) - 1
                If $a8[$h] = $a1 Or $a8[$h] = $a2[$b] Or $a8[$h] = $a3[$c] Or $a8[$h] = $a4[$d] Or $a8[$h] = $a5[$e] Or $a8[$h] = $a6[$f] Or $a8[$h] = $a7[$g] Then ContinueLoop
                $resArr[7] = $a8[$h]
                $sorArr = $resArr
                _ArraySort($sorArr)
                $outStr &= $sorArr[0] & "," & $sorArr[1] & "," & $sorArr[2] & "," & $sorArr[3] & "," & $sorArr[4] & "," & $sorArr[5] & "," & $sorArr[6] & "," & $sorArr[7] & @CRLF
              Next
            Next
          Next
        Next
      Next
    Next
    FileWrite($hFile, $outStr)
    $outStr = ""
  Next
  FileClose($hFile)
EndFunc   ;==>Check

You can find my multi-threading UDF in my signature.

ps.  I was able to reduce it to 12 secs but rewriting the _ArraySort to fit the situation (not included)...

Thanks for your reply. I handle the issue similar to your approach. I handle Array unique with my function (instead of using ArrayUnique). Also, using Scripting.Dictionary to perform de-duplication. I post pseudo code instead of real code because my code contain a lot of un-related section and I am lazy to remove them ;>

 

Now I am wonder how to remove dictionary object (instead of use Dictionary.Remove item by item, any ways to remove all at once ?)

[Nine]

42 minutes ago, CFLam said:

Now I am wonder how to remove dictionary object (instead of use Dictionary.Remove item by item, any ways to remove all at once ?)

You should post a snippet of your code so we can see how you handle it.  Without code, it is just a guessing game. 
Effort can pay off, laziness will rarely do.  

Edited Friday at 03:52 PM by Nine

[pixelsearch]

1 hour ago, CFLam said:

Now I am wonder how to remove dictionary object (instead of use Dictionary.Remove item by item, any ways to remove all at once ?)

When I discovered Scripting.Dictionary in 2023, the first thing I did was to download some explanations & syntax from MS site, then keep them in separate text files :

As you can see, there is a method to remove at once all key/item pairs from a Dictionary object.
Good luck

[Numeric1]

4 hours ago, CFLam said:

Now I am wonder how to remove dictionary object (instead of use Dictionary.Remove item by item, any ways to remove all at once ?)

I think @pixelsearch already answered the question well.

If your goal is simply to clear the contents of the dictionary while keeping the object itself, then the RemoveAll method will do the job — and trust me, it’s fast, no matter how many elements are inside.

On the other hand, if your goal is to free up resources, including the dictionary object itself, then just release it ($oDict = 0). AutoIt will take care of the rest.

[pixelsearch]

1 hour ago, Numeric1 said:

If your goal is simply to clear the contents of the dictionary while keeping the object itself, then the RemoveAll method will do the job — and trust me, it’s fast, no matter how many elements are inside.

I second that, having used it plenty of times while in a loop, in this script . OP was happy with the speed of the script

[Nine]

You can simply :

$oDict = 0

But the my intention was to understand the algorithm of OP, to provide proper solution that might have nothing to do with dictionary...

[CFLam]

16 hours ago, pixelsearch said:

When I discovered Scripting.Dictionary in 2023, the first thing I did was to download some explanations & syntax from MS site, then keep them in separate text files :

As you can see, there is a method to remove at once all key/item pairs from a Dictionary object.
Good luck

You are right, should keep the url in my bookmark:

https://learn.microsoft.com/en-us/office/vba/language/reference/user-interface-help/dictionary-object

[CFLam]

13 hours ago, Numeric1 said:

I think @pixelsearch already answered the question well.

If your goal is simply to clear the contents of the dictionary while keeping the object itself, then the RemoveAll method will do the job — and trust me, it’s fast, no matter how many elements are inside.

On the other hand, if your goal is to free up resources, including the dictionary object itself, then just release it ($oDict = 0). AutoIt will take care of the rest.

Yes, thanks. Got it. Seems that the dictionary object can replace the array of AutoIt...

[CFLam]

11 hours ago, Nine said:

You can simply :

$oDict = 0

But the my intention was to understand the algorithm of OP, to provide proper solution that might have nothing to do with dictionary...

I use RemoveAll eventually.