ferradavi

Finding all possible combinations of numbers to reach a given sum

52 posts in this topic

#1 ·  Posted (edited)

Any ideas about writing fast code finding all possible combinations of numbers to reach a given sum (target) in a matrix???

example: Target 12

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

[2,6,5,5,2,1,1,9]

[1,4,5,1,2,1,4,3]

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

[6,8,5,9,2,1,4,6]

 

All possible combinations: 7+5, 7+3+2, 7+1+4, 8+3+1, and so on....

Thanks !!!

Edited by ferradavi

Share this post


Link to post
Share on other sites



#3 ·  Posted (edited)

ferradavi,

Welcome to the AutoIt forums.

An interesting little problem. This code seems to work:

#include <Array.au3>

$iRequiredSum = 12

Global $aArray = [7, 8, 5, 3, 2, 1, 4, 6]

; Increase the number of factors on each pass
For $iSet = 1 To UBound($aArray)
    ; Determine the possible combinations
    $aCombinations = _ArrayCombinations($aArray, $iSet, "+")
    ; For each combination
    For $j = 1 To $aCombinations[0]
        ; Break into factors
        $aFactors = StringSplit($aCombinations[$j], "+")
        ; Sum factors
        $iSum = 0
        For $k = 1 To $aFactors[0]
            $iSum += $aFactors[$k]
        Next
        ; If sum is required value
        If $iSum = $iRequiredSum Then
            ; Write caombination
            ConsoleWrite($aCombinations[$j] & " = " & $iRequiredSum & @CRLF)
        EndIf
    Next
Next

The result:

7+5 = 12
8+4 = 12
7+3+2 = 12
7+1+4 = 12
8+3+1 = 12
5+3+4 = 12
5+1+6 = 12
2+4+6 = 12
5+2+1+4 = 12
3+2+1+6 = 12

Please ask if you have any questions.

M23

Edited by Melba23
Typo

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites
26 minutes ago, JohnOne said:

Looks like a difficult math problem that one.

I'm curious, is there is a practical purpose to this?

Yep... Avoid using excel

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

2 hours ago, Melba23 said:

 

That's pretty cool Melba23 !! ;-D

What about to consider only one solution (the first one possible) for a specific number of factors and skip to the next one:

i.e.  

7+5, (the first possible for 2 factors)

7+3+2, (the first possible for 3 factors)

5+2+1+4 (the first possible for 4 factors)

Thanks!!!!!!

Edited by Melba23
Removed quote

Share this post


Link to post
Share on other sites

ferradavi,

When you reply, please use the "Reply to this topic" button at the top of the thread or the "Reply to this topic" editor at the bottom rather than the "Quote" button - I know what I wrote and it just pads the thread unnecessarily.

As to just displaying the first result for each number of factors this looks as if it does what you want:

#include <Array.au3>

$iRequiredSum = 12

Global $aArray = [7, 8, 5, 3, 2, 1, 4, 6]

; Increase the number of factors on each pass
For $iSet = 1 To UBound($aArray)
    ; Determine the possible combinations
    $aCombinations = _ArrayCombinations($aArray, $iSet, "+")
    ; For each combination
    For $j = 1 To $aCombinations[0]
        ; Break into factors
        $aFactors = StringSplit($aCombinations[$j], "+")
        ; Sum factors
        $iSum = 0
        For $k = 1 To $aFactors[0]
            $iSum += $aFactors[$k]
            ; Are we over the required sum?
            If $iSum > $iRequiredSum Then
                ; No point in adding further factors <<<<<<<
                ExitLoop
            EndIf 
        Next
        ; If sum is required value
        If $iSum = $iRequiredSum Then
            ; Write first combination found for this number of factors <<<<<<<<<
            ConsoleWrite("For " & $iSet & " factors" & @CRLF & $aCombinations[$j] & " = " & $iRequiredSum & @CRLF)
            ; Move immediately to increase the number of factors <<<<<<<<<
            ExitLoop
        EndIf
    Next
Next

Result:

For 2 factors
7+5 = 12
For 3 factors
7+3+2 = 12
For 4 factors
5+2+1+4 = 12

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

Sorry...

Thank you for your precious help!

Share this post


Link to post
Share on other sites
On 15/2/2016 at 2:31 PM, ferradavi said:

Sorry...

Thank you for your precious help!

Hi Melba23,

I'm in a trouble  :'(:sweating:

When I use the script in a 9x9 grid it runs so slow.

Expecially if the number of factors is 4.  If higher I get "Array maximum size exceeded"..

Do you have any suggestion to find only the first solution useful to get the target, skipping all possible combinations?

Thanks :>

 

grid.au3

Share this post


Link to post
Share on other sites

ferradavi,

The error is obvious - line #345 is completely wrong!

 

 

If you want a sensible answer, how about posting the code you are using - see here how to do it

M23

 


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

Thank you... That's it!

#include <Array.au3>

$iRequiredSum = 27

Global $aArray = [1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9, _
                  1,2,3,4,5,6,7,8,9]

; Increase the number of factors on each pass
For $iSet = 1 To UBound($aArray)
    ; Determine the possible combinations
    $aCombinations = _ArrayCombinations($aArray, $iSet, "+")
    ; For each combination
    For $j = 1 To $aCombinations[0]
        ; Break into factors
        $aFactors = StringSplit($aCombinations[$j], "+")
        ; Sum factors
        $iSum = 0
        For $k = 1 To $aFactors[0]
            $iSum += $aFactors[$k]
            ; Are we over the required sum?
            If $iSum > $iRequiredSum Then
                ; No point in adding further factors <<<<<<<
                ExitLoop
            EndIf
        Next
        ; If sum is required value
        If $iSum = $iRequiredSum Then
            ; Write first combination found for this number of factors <<<<<<<<<
            ConsoleWrite("For " & $iSet & " factors" & @CRLF & $aCombinations[$j] & " = " & $iRequiredSum & @CRLF)
            ; Move immediately to increase the number of factors <<<<<<<<<
            ExitLoop
        EndIf
    Next
Next

 

Do you have any suggestion to find only the first solution useful to get the target number?

 

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

ferradavi,

That is not a 9x9 grid - that is a single list of 81 elements. So it is hardly surprising that you run into problems as the possible number of small set-size combinations of those 81 elements is extremely large.

So let us see if we can approach this a different way, but first I need some more information:

  • Are those values representative - i.e. are they always integers from 1 to 9?
  • Is there any limit to the number of repeat instances for any element - can there be anywhere between 0 or 81 repeats?

M23

 

Edited by Melba23
Formatting

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

#13 ·  Posted (edited)

Ok

Yes they are always integers from 1 to 9, but they are generated in a random way and order.

It's sufficient to obtain one result, the first one possible to get the target number. If the target is between 2 to 18, obviously two factors are good...and also fast

To get an higher target number, such as 27, the number of factors starts from 3, but if there aren't 3 elements in the list the number of factors must be higher: 4, 5, 6 etc.

i.e. to obtain 27, if I start from the first element in the list: 

Global $aArray = [1,2,2,3,1,1,6,3,4, _
                  4,2,3,4,5,6,7,8,9, _
                  7,2,3,4,5,1,7,2,9, _
                  9,2,3,9,5,5,7,1,9, _
                  3,2,1,2,3,6,6,6,4, _
                  3,2,3,4,5,6,7,8,9, _
                  2,2,3,8,1,4,7,1,9, _
                  1,7,3,9,5,6,7,1,2, _
                  7,2,3,7,5,1,7,8,5]

 

I have minimum 3 factors = 9+9+9 (infact I cannot obtain 27 with only 2 factors).

In the next example the solution cannot be reached from the sum of 3 factors, because there are only 2 elements marked 9 (the first and the last)... so to obtain 27 it's necessary to consider the sum of 4 factors and if we cannot obtain the target in this way it's necessary to consider the sum of 5 factors and so on. The target can be an integer from 11 to 100.

Global $aArray = [9,2,2,3,1,1,6,3,4, _
                  4,2,3,4,5,6,7,8,7, _
                  7,2,3,4,5,1,7,2,2, _
                  2,2,3,1,5,5,7,1,4, _
                  3,2,1,2,3,6,6,6,4, _
                  3,2,3,4,5,6,7,8,3, _
                  2,2,3,8,1,4,7,1,2, _
                  1,7,3,5,5,6,7,1,2, _
                  7,2,3,7,5,1,7,8,9]

Which is the fastest way to do this?

Edited by ferradavi

Share this post


Link to post
Share on other sites

ferradavi,

You are introducing more and more constraints on this problem - before I devote any more time to trying to solve this, please explain why you need to do this.

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

here is a long way to determine factors, certainly not optimal

;arrayFactors
#include<array.au3>

$target = 27

Global $aArray = [9,2,2,3,1,1,6,3,4, _
                  4,2,3,4,5,6,7,8,7, _
                  7,2,3,4,5,1,7,2,2, _
                  2,2,3,1,5,5,7,1,4, _
                  3,2,1,2,3,6,6,6,4, _
                  3,2,3,4,5,6,7,8,3, _
                  2,2,3,8,1,4,7,1,2, _
                  1,7,3,5,5,6,7,1,2, _
                  7,2,3,7,5,1,7,8,9]

$aWork = $aArray

$max1 = _ArrayMaxIndex($aWork , 1)
        _ArrayDelete($aWork , $max1)

$max2 = _ArrayMaxIndex($aWork , 1)
        _ArrayDelete($aWork , $max2)

If $aArray[$max1] + $aArray[$max2] >= $target Then
    msgbox(0, '' , "2 factor min")
Else
    $max3 = _ArrayMaxIndex($aWork , 1)
        _ArrayDelete($aWork , $max3)
EndIf


If $aArray[$max1] + $aArray[$max2] + $aArray[$max3] >= $target Then
    msgbox(0, '' , "3 factor min")
Else
    $max4 = _ArrayMaxIndex($aWork , 1)
        _ArrayDelete($aWork , $max4)
EndIf

If $aArray[$max1] + $aArray[$max2] + $aArray[$max3] + $aArray[$max4] >= $target Then
    msgbox(0, '' , "4 factor min")
Else
    $max5 = _ArrayMaxIndex($aWork , 1)
        _ArrayDelete($aWork , $max5)
EndIf

 


,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

ferradavi,

With a little lateral thinking I have a really good, fast solution to the problem, but I am still awaiting an explanation as to why you need to do this.

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

shrunk mine some

;arrayFactors
#include<array.au3>

$target = 27

Global $aArray = [9,2,2,3,1,1,6,3,4, _
                  4,2,3,4,5,6,7,8,7, _
                  7,2,3,4,5,1,7,2,2, _
                  2,2,3,1,5,5,7,1,4, _
                  3,2,1,2,3,6,6,6,4, _
                  3,2,3,4,5,6,7,8,3, _
                  2,2,3,8,1,4,7,1,2, _
                  1,7,3,5,5,6,7,1,2, _
                  7,2,3,7,5,1,7,8,9]

$aWork = $aArray
_ArraySort($aWork , 1)

for $i = 2 to ubound($aWork)
$total = execute(_ArrayToString($aWork , "+" , -1 , $i))
    If $total >= $target then
        msgbox(0, '' , "minimum of " & $i & " factors")
        Exit
    EndIf
next

 


,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

This is a difficult math problem we discuss in our classes to develop a smart, fast and efficient algorithm.

 

Share this post


Link to post
Share on other sites

ferradavi,

Fine. My "lateral thinking" led me to the idea that to minimize the number of factors required you should use as many of the higher value ones as possible and then use the smaller ones to "fill in". So that is what happens in this script:

#include <Array.au3>
#include <MsgBoxConstants.au3>

Local $iMaxPossible = 0

; Create random 81 elements and calculate eh max possible value
Global $aFactors[81]
For $i = 0 To 80
    $aFactors[$i] = Random(1, 9, 1)
    $iMaxPossible += $aFactors[$i]
Next

; Determine required number
$iRequired = Random(1, $iMaxPossible, 1)
ConsoleWrite("Required: " & $iRequired & @CRLF)

;_ArrayDisplay($aFactors, "", Default, 8)

; Count number of each separate element
Global $aFactorCount[10]
For $i = 0 To 80
    $aFactorCount[$aFactors[$i]] += 1

Next

;_ArrayDisplay($aFactorCount, "", Default, 8)

; Declare variables
Local $iTotal = 0, $iRemainder = $iRequired, $sFactors = ""

; Starting with the highest element
For $iFactorValue = 9 To 1 Step -1
    ; How many can be used to reach the required value
    $iFactorReq = Int($iRemainder / $iFactorValue)
    ; if there are not enough, then only use the available number
    If $iFactorReq > $aFactorCount[$iFactorValue] Then
        $iFactorReq = $aFactorCount[$iFactorValue]
    EndIf
    ; Adjust values for next pass and create result string
    For $j = 1 To $iFactorReq
        $iTotal += $iFactorValue
        $iRemainder -= $iFactorValue
        $sFactors &= $iFactorValue & "+"
    Next
    ; if required total reached then stop
    If $iTotal = $iRequired Then
        ExitLoop
    EndIf

Next

If $iTotal = $iRequired Then
    ConsoleWrite(StringTrimRight($sFactors, 1) & "=" & $iRequired & @CRLF)
Else
    ConsoleWrite("Unable to factor " & $iRequired & @CRLF)
EndIf

_ArrayDisplay($aFactorCount, "", Default, 8)

I hope the comments are sufficiently clear, but please ask if not.

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

This is the classical problem in additive number theory (also called additive combinatorics theory).


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

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