# Finding all possible combinations of numbers to reach a given sum

## Recommended Posts

M23,

I see. Ok!

@iamtheky very interesting solution.

• Replies 51
• Created

#### Popular Posts

The standard answer for small-scale problems is essentially brute-force. Of course one hits a computability wall when the scale grows significantly. Algorithms used for certain variants of the knapsac

I modified the list in a 2d array, 8x8 grid and I defined the target number between 11 and 50.

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

Local \$iMaxPossible = 0

;Create random 64 elements and calculate the max possible value
Global \$aFactors[8][8]

For \$i = 0 To 7
For \$ii = 0 To 7
\$aFactors[\$i][\$ii] = Random(1, 9, 1)
\$iMaxPossible += \$aFactors[\$i][\$ii]
Next
Next

; Determine required number
\$iRequired = Random(11,50,1)

ConsoleWrite("Required: " & \$iRequired & @CRLF)

Global \$aFactorCount[10]

For \$i = 0 To 7
For \$ii = 0 To 7
\$aFactorCount[\$aFactors[\$ii][\$i]] += 1
Next
Next

; 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

_ArrayDisplay(\$aFactors,"8x8 Grid")
;_ArrayDisplay(\$aFactorCount, "", Default, 8)

If \$iTotal = \$iRequired Then
ConsoleWrite(StringTrimRight(\$sFactors, 1) & "=" & \$iRequired & @CRLF)
MsgBox(0,"Solution",StringTrimRight(\$sFactors, 1)& "=" & \$iRequired)
Else
ConsoleWrite("Unable to factor " & \$iRequired & @CRLF)
MsgBox(0,"No Solution","Unable to factor")
EndIf```

I'd like to update the 2D array when the target is reached:

i.e. assuming that:

1. the starting grid (2d array), randomly generated, is the first file I attached below (8x8 grid original.bmp),
2. and the target number is 44

the result is:

9+9+9+9+8 = 44

How can I get (re-write) the 2D array I attached as second image (8x8 grid update.bmp) where the remaining elements are slid down in the column (not only deleted).

Then, I'd like to re-start the script using a loop, drawing another random target number and so on till the end: a funny and simple auto-solving mathematical game.

Thank you!

##### Share on other sites

As promised, here's my take on this.

My Contributions and Wrappers

Spoiler
##### Share on other sites

Agreed SA can be used in general for finding a solution in similar contexts, well unless it fails to. Yet that doesn't answer the OP original question (find all solutions). SA is also pretty hard to analyze computationally and be proven to succeed, if at all.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
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 on other sites

@jchd: I already mentioned in post#27 in this thread that SA yields a single solution per run, and the OP mentioned this as alternate requirement after their initial post. As to your other points, you're definitely right that SA is hard to analyse, and cannot be proven to succeed (and I never claimed this). But I'm coming at this from a more practical perspective, based upon my own work using SA to come up with reasonable solutions that balance many conflicting requirements in a high-dimensional solution space, before the universe dies of heat-death. And if you run my first SA example a few times, you can see that in this particular case. most often it does come up with one of the several optimal solutions (exact target match + minimum number of terms). If the only other alternative is brute-force, and brute-force is going to take forever and a day, then I'll settle for anything that gives me a decent chance at a good estimate, even if its success is not guaranteed. I agree that it may be impossible to determine in advance how likely an acceptable outcome is. But the time gain w.r.t. brute-force can be so gargantuan that one can easily run dozens or hundreds of SA estimates to explore the SA solution space to get a sense of its distribution. Plus, I like the simplicity of the algorithm, wich is of course completely subjective.

Edited by RTFC

My Contributions and Wrappers

Spoiler
##### Share on other sites

@RTFC Extremely refined!!!

##### Share on other sites
On 20/2/2016 at 11:58 PM, iamtheky said:

Is this accurate (other than random, that cant be right, if you could fix that it would be super), I am doing my best at brute forcing my way there

All attempts take the same amount of time, and there are certainly results that seem mathishly correct.

```;BruteForceFactory(BFF)
#include<array.au3>

;~ \$target = 110
\$target = 50
;~ \$target = 9

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]

\$aWork = \$aArray
_ArraySort(\$aWork , 1)
\$last = ""
\$count = 0

for \$k = ubound(\$aWork) - 1 to 0 step - 1
tooltip(\$count , 0 ,0 )

If \$count = ubound(\$aArray) * ubound(\$aArray) Then exitloop

\$total = \$k <> 0 ? _ArrayToString(\$aWork , "+" , 0 , \$k) : \$aWork[0]

If execute(\$total) = number(\$target) then
EndIf

If \$k = 0 Then
\$aWork = \$aArray
\$count += 1
_ArraySwap(\$aWork , 0 , mod(\$count , ubound(\$aWork) - 1))
\$k = ubound(\$aWork) - 1
Else
_ArrayDelete(\$aWork , random(0 , ubound(\$aWork) - 1 , 1))
EndIf
next

If ubound(\$aAnswers) < 1 Then msgbox(0, '' , 'no match')

@iamthekyCould you explain me how does it work?

##### Share on other sites

@ferradavi: Thanks (didn't invent this though, just ported it to AutoIt). However, jchd is quite right in stressing this is not a fix-all, and it won't yield all permutations as you requested in your first post. Also, SA's efficacy and efficiency depend sensitively on the way you define and balance your cost functions; sometimes it can take a fair bit of fiddling before the algorithm starts finding what one wants it to find, rather than what one apparently instructed it to find. It all depends on the type of problem you're tackling.

Furthermore, I should have mentioned that if you change the target value in my test example 1 (the one that handles your scenario), you may have to also adjust the \$minsumlength accordingly (so for example, if your target value is set to 12, \$minsumlength would become 1 (base-0, so minimum two values to sum)). Anyway, have fun playing with it.

Edited by RTFC

My Contributions and Wrappers

Spoiler
##### Share on other sites

Exactly: "know your data" is a pretty imperative prerequisite to using SA successfully since you can esily obtain surprisingly fast but poor results if you don't parametrize the search by means of suitable costs evaluators. That's why I never recommend SA to unexperienced audience. For French readers, SA translates as "recuit simulé", due to similarity with the rearrangement of atoms in crytals of some metals (e.g. copper) or alloys after fusion, cooling, re-heating to lower temp and re-cooling.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
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 on other sites

@jchd: you're right, but I would argue that "know your data" applies pretty much across the board, regardless of what optimisation/minimisation algorithm you apply. And experienced audiences often make the same mistake, for example applying Gaussian-based statistics on distinctly non-Gaussian datasets, or attempting to invert a strongly underdetermined system. I like SA because it forces me to explicitly express my cost functions and thereby consider carefully how these expressions translate into whatever optimum I'm seeking. And when the outcome is unexpected/oviously wrong, the algorithm is also so simple that even a beginner can tinker with it (for example, by adjusting weights and scaling), whereas more sophisticated methods (e.g., downhill simplex, conjugate gradient) may be completely inscrutable  to someone without a solid maths background. In that sense, SA can be a good learning experience to get to know your problem better, at least that's how it works for me. But of course, no such method should ever be used as a black-box; I'm with you on that one.

Edited by RTFC
typo

My Contributions and Wrappers

Spoiler
##### Share on other sites

@iamthekyCould you explain me how does it work?

It iterates through the array X number of times (where x is the ubound * ubound).  after every iteration deletes a random element, after every full loop it resets the array and swaps out my starting element.   Hopefully getting enough variations of the data set to capture the targets.

Edited by iamtheky

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

##### Share on other sites

@iamtheky That's really amazing!

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
×
• Create New...