Finding all possible combinations of numbers to reach a given sum

[ferradavi]

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 February 24, 2016 by ferradavi

[JohnOne]

Looks like a difficult math problem that one.

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

[Melba23]

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 February 15, 2016 by Melba23
Typo

[ferradavi]

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

[ferradavi]

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 February 15, 2016 by Melba23
Removed quote

[jguinch]

Just add ExitLoop after the ConsoleWrite line.

 

[Melba23]

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

[ferradavi]

Sorry...

Thank you for your precious help!

[ferradavi]

On 15/2/2016 at 2:31 PM, ferradavi said:

Sorry...

Thank you for your precious help!

Hi Melba23,

I'm in a trouble  

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

[Melba23]

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

 

[ferradavi]

Thank you... That's it!

expandcollapse popup

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

 

[Melba23]

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 February 19, 2016 by Melba23
Formatting

[ferradavi]

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 February 19, 2016 by ferradavi

[Melba23]

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

[iamtheky]

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

expandcollapse popup

;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

 

[Melba23]

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

[iamtheky]

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

 

[ferradavi]

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

 

[Melba23]

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:

expandcollapse popup

#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

[jchd]

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