Interesting Programming Problem

[Jeff Grippe]

Hi All,

Thanks in advance for the help.

This is more of a general programming problem rather than a FoxPro problem
but since I work in FoxPro I thought I'd see if any of you had any
interesting ideas. Brute force is probably going to be the way to go,
however.

I have a data with amount fields. Lets say that they are in an array because
you wouldn't want to do this against something disk based.

The number of records (or array rows) is no more than 100 and is probably
going to be around 20-40 most of the time.

The user enters an amount and I need to find all combinations of records
whose amount fields total up to the amount entered. It can be 1 row or it
could be 20 rows that total to this amount. Most of the time there will be
only one solution. I might have additional data such as dates that can
simplify this problem but I don't know yet that that data can be relied
upon.

Does anyone have any thoughts on the code for finding all combinations of
one or more amounts that total to a specific value? I know that it is going
to require nested loops but the fact that the solution(s) can be a variable
number of amounts is a bit confusing to me.

Thanks,
Jeff

[Jürgen Wondzinski]

Hi Jeff

I once had to solve a similar problem ;) I my case it was tablebased (of
course: we are in FoxPro, so why use arrays, a cursor is much more
efficient!)

I built an index on the amount field, and first searched for an entry which
was exact or smaller as that value. You can do this with SET ORDER ASCENDING
and SET NEAR ON, then you get the next fitting match. With the calculated
difference between needed amount and found amount you do the next search,
until there is no amount left (the ideal case). Normally you will be faced
with the possibility that there is no matching amount left (maybe because
they're all bigger than the needed rest) in that case I cancel the last
found record and use the next smaller one, and do the loop again.

You should use a allowed range for the allowed match, maybe "if the sum of
all found records comes close to +/- 5% of the value" then the job is
done...

--

Juergen Wondzinski

Microsoft Visual FoxPro Evangelist
Microsoft Most Valuable Professional since 1996
"*´¨)
¸.•´¸.•*´¨) ¸.•*¨)
(¸.•´. (¸.•` *
.•`.Visual FoxPro: It's magic !
(¸.•``••*

[Olaf Doschke]

A rather straight forward approach would be

sort the array of amounts descending

with some total amount you want to match with a sum of sub amounts
a) find the largest sub amount smaller than or equal to the total amount
b) subtract that and recurse (begin again) with the
new total amount = old total amount - sub amount.
you do not need to restart in the array of sub amounts
of course, as the new total amount is smaller.

If the new total amount=0 you have a solution.

If the new total amount is smaller than the smallest sub amount available
you can't have a solution with the rest of amounts.

If the new total amount is larger than the sum of available sub amounts
you also can't have a solution with the rest of amounts.

To find other solutions you try without the first,
largest sub amount you found, so you restart with
a subarray excluding that first used sub amount
and all larger amounts of course.

Bye, Olaf.

[Al Marino]

good answer

small correction
after a check with one value
1. save if solution
2. advance to next index and try again
solution may be (1) + (3) +(4) and also (1) +(3)+(6)+(7)

also, I would not check sum as would have recalc sum each
iteration

al

"Olaf Doschke"
<b2xhZi5kb3NjaGt...@strconv.14.de> wrote in
message news:%23ox4I5A...@TK2MSFTNGP02.phx.gbl...

[Olaf Doschke]

> also, I would not check sum as would have recalc sum each iteration

Well, you would only need to calc
the sum of subtotals up to a certain
subtotal in the array once, eg:

subtotal / sum of remaining subtotal:
100 / 175
50 / 75
25 / 25

start with 200
find 100 but also sum(rest)=175
which means 200 has no exact solution.

start with 180
find 100, continue with rest of 80
find 50 but also sum(rest)=75,
which means 180 has no exact solution.

You found my other flaw, wOOdy has
that better already.

Bye, Olaf.

[Olaf Doschke]

> subtotal / sum of remaining subtotal:
> 100 / 175
> 50 / 75
> 25 / 25
>
> start with 200
> find 100 but also sum(rest)=175
> which means 200 has no exact solution.
>
> start with 180
> find 100, continue with rest of 80
> find 50 but also sum(rest)=75,
> which means 180 has no exact solution.

Well, both bad examples of course, as
the max sum is 175 anyway.

start with 170, 130 or whatever,
you see the principle...

Bye, Olaf.

[Gene Wirchenko]

"Jeff Grippe" <je...@door7.com> wrote:

>Thanks in advance for the help.
>
>This is more of a general programming problem rather than a FoxPro problem
>but since I work in FoxPro I thought I'd see if any of you had any
>interesting ideas. Brute force is probably going to be the way to go,
>however.

Yes, it is.

>I have a data with amount fields. Lets say that they are in an array because
>you wouldn't want to do this against something disk based.

It looks as if you are doing invoice reconciliation or something
similar.

What are the amounts' signs? If it is only one sign, then it is
easier. If there are positive and negative amounts, it is messier.

If there is the possibility of incorrect amounts, it is even
worse. Casting out nines may or may not help.

[snip]

>Does anyone have any thoughts on the code for finding all combinations of
>one or more amounts that total to a specific value? I know that it is going
>to require nested loops but the fact that the solution(s) can be a variable
>number of amounts is a bit confusing to me.

For one sign, sort from highest to lowest. Then select the
largest possible value that is not too big and keep doing that as long
as possible. You may find a solution. If not, back off a step, and
try the next possibility. Eventually, you will get through them all.
It will work as in the example below:

Example:
5, 8, 16, 14, 7, 2 with a target of 20

Sorted:
16, 14, 8, 7, 5, 2

Run:
Pick 16. Reject 14, 8, 7, 5. Pick 2. No more data: back off 2. No
more data: back off 16.

Pick 14. Reject 8, 7. Pick 5. Reject 2. No more data: back off 5.
Pick 2. No more data: back off 2. No more data: back off 14.

Pick 8, 7, 5. SOLUTION. If you want all solutions, continue. Back
off 5. Pick 2. No more data: back off 2. No more data: back off 7.
Pick 5, 2. No more data: back off 2. No more data: back off 5. Pick
2. No more data: back off 2. No more data: back off 8.

Pick 7, 5, 2. No more data: back off 2. No more data: back off 5. No
more data: back off 7.

Pick 5, 2. No more data: back off 2. No more data: back off 5.

Pick 2. No more data: back off 2. No more data: end.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.

[Jeff Grippe]

I love the approach that has been contributed by a number of people. It is
clever and shows some good thinking.

The problem I have with it is that the amounts I have to add up to the total
I have are almost always going to be smaller than the total so indexed
seeking approach will just about always turn into a brute force approach.

With that as a given, I think it probably going to be best to brute force it
from data in memory and not on disk.

The part I'm having a hard time figuring out how to code has to do with the
fact that the sum can be made up of from 1 - n values. It seems like a good
application for recursion although I've never been good at thinking that
way.

I'll keep working on it.

Thanks,
Jeff
"Gene Wirchenko" <ge...@ocis.net> wrote in message
news:mnjo34po7k8funr1e...@4ax.com...

[Olaf Doschke]

> The problem I have with it is that the amounts I have to add up to the total
> I have are almost always going to be smaller than the total so indexed
> seeking approach will just about always turn into a brute force approach.

Hmm, wasn't that clear from the ouline?
Perhaps I don't get your thought here.

brute force would be picking any
combination of amounts to make
up the total. You're much better off
using a sorted list of amounts, which
will save you from testing many impossible
combinations.

Bye, Olaf.

[Jeff Grippe]

"Olaf Doschke" <olaf.d...@t-aufderlinie.de> wrote in message
news:1D07A5CD-877F-4114...@microsoft.com...

I see your point here but I'm dealing with a relatively small number of
numbers. Of course once you say that you immediately get someone who wants
to use your application with a large data set.

So using the sorted list (which can still be in memory), you are saying that
you can avoid looking at numbers that will put you over your total by
searching the sorted list. I think that the coding gets very complex. I'll
have to see if I can metacode something, post it, and let people comments.

Thanks,
Jeff

[Gene Wirchenko]

"Jeff Grippe" <je...@door7.com> wrote:

[snip]

>I see your point here but I'm dealing with a relatively small number of
>numbers. Of course once you say that you immediately get someone who wants
>to use your application with a large data set.

You are dealing with factorials here. They get very big very
fast. 10! is well over one million. That makes ten a big number
relatively speaking. How much data do you have?

>So using the sorted list (which can still be in memory), you are saying that
>you can avoid looking at numbers that will put you over your total by
>searching the sorted list. I think that the coding gets very complex. I'll

You do not search, but rather increment indexes. Actually, it
does not get complex. I already outlined the algorithm. It is little
more complicated than nested loops.

>have to see if I can metacode something, post it, and let people comments.

Sincerely,

[Olaf Doschke]

> You are dealing with factorials here. They get very big very
> fast. 10! is well over one million. That makes ten a big number
> relatively speaking. How much data do you have?

Correct.

Jeff, you told about 20-40 amounts here
that can be combined.

Lets say it's only 20.
In a brute force way you would chose

step 1: one of 20 amounts, so 20 options for step 1...
step 2: one of the remaining 19 amounts, 19 options...
step 3: one of the remaining 18 amounts, 18 options...
...

That's 20! = 20x19x18x...
2432902008176640000
combinations.

You won't need to check all, in a simple case, eg
total amount = sum of the 20 amounts it even does
not matter how you pick the amounts, after 20
picks you will have the solution.

But mostly you may have a sum of 2-5 amounts
perhaps. If the first pick is blind and not fitting you'll
check millions of billions of combinations without having
a solutions.

So you better sort your amounnts and use the outlined
algorithm.

It's a recursive thing.

You find a solution to the initial problem
by finding a first best guess for the first
amount you choose, reduce the total
amount and the array of available elements
(by marking that amount as picked)
Then call yourself with the reduced
problem of finding a reduced totalamount
with one less element in the array.

Bye, Olaf.

[Al Marino]

for this particular case (searching for a specific total)
it is better to sort in ascending order, that way you stop
when sum > total
in your example, 10 checks vs 17 (depending how you count)

al

"Gene Wirchenko" <ge...@ocis.net> wrote in message
news:mnjo34po7k8funr1e...@4ax.com...

[Jeff Grippe]

"Gene Wirchenko" <ge...@ocis.net> wrote in message

news:qsor34thvsfn41m5s...@4ax.com...

> "Jeff Grippe" <je...@door7.com> wrote:
>
> [snip]
>
>>I see your point here but I'm dealing with a relatively small number of
>>numbers. Of course once you say that you immediately get someone who wants
>>to use your application with a large data set.
>
> You are dealing with factorials here. They get very big very
> fast. 10! is well over one million. That makes ten a big number
> relatively speaking. How much data do you have?
>

> You do not search, but rather increment indexes. Actually, it
> does not get complex. I already outlined the algorithm. It is little
> more complicated than nested loops.
>

>>>Run:
>>>Pick 16. Reject 14, 8, 7, 5. Pick 2. No more data: back off 2. No
>>>more data: back off 16.

>>>Pick 14. Reject 8, 7. Pick 5. Reject 2. No more data: back off 5.
>>>Pick 2. No more data: back off 2. No more data: back off 14.

Your algorithm is still dealing with factorials because in order to reject
the numbers you are rejecting you must consider them. I'm not sure if your
algorithm allows you to not consider higher numbers once you have rejected
them in a pass through the loop. This may be a problem for which the human
brain is better suited.

What I can add to the problem description is:
1. There will always be a solution (although you must code for the "no
solution" case)
2. The numbers will all always be positive

I'm going to play with your algorithm a bit more a bit more. I've been
wondering if there were some algorithm where you start with the sum of the
data set and then use subtraction to find your answer.

Thanks,
Jeff

[Gene Wirchenko]

"Jeff Grippe" <je...@door7.com> wrote:

>
>"Gene Wirchenko" <ge...@ocis.net> wrote in message
>news:qsor34thvsfn41m5s...@4ax.com...
>> "Jeff Grippe" <je...@door7.com> wrote:
>>
>> [snip]
>>
>>>I see your point here but I'm dealing with a relatively small number of
>>>numbers. Of course once you say that you immediately get someone who wants
>>>to use your application with a large data set.
>>
>> You are dealing with factorials here. They get very big very
>> fast. 10! is well over one million. That makes ten a big number
>> relatively speaking. How much data do you have?
>>
>> You do not search, but rather increment indexes. Actually, it
>> does not get complex. I already outlined the algorithm. It is little
>> more complicated than nested loops.
>>
>>>>Run:
>>>>Pick 16. Reject 14, 8, 7, 5. Pick 2. No more data: back off 2. No
>>>>more data: back off 16.
>
>>>>Pick 14. Reject 8, 7. Pick 5. Reject 2. No more data: back off 5.
>>>>Pick 2. No more data: back off 2. No more data: back off 14.
>
>Your algorithm is still dealing with factorials because in order to reject
>the numbers you are rejecting you must consider them. I'm not sure if your
>algorithm allows you to not consider higher numbers once you have rejected
>them in a pass through the loop. This may be a problem for which the human
>brain is better suited.

Higher numbers, once they are incremented past, will not be
considered.

No, not as a general solution. If you accept close
approximations, then possibly.

>What I can add to the problem description is:
>1. There will always be a solution (although you must code for the "no
>solution" case)

Not for the exact sum version.

By the ordering principle, there will always be a best answer. By
your definition (being close), this is a solution.

>2. The numbers will all always be positive

Then use my approach.

>I'm going to play with your algorithm a bit more a bit more. I've been
>wondering if there were some algorithm where you start with the sum of the
>data set and then use subtraction to find your answer.

That is isomorphic to my algorithm. Whether you add up to the
desired number and watch for sums too big or subtract from the desired
number and watch for differences less than zero, it is the same
general idea.

[Gene Wirchenko]

"Al Marino" <almarino_AT_intelliform.net> wrote:

>for this particular case (searching for a specific total)
>it is better to sort in ascending order, that way you stop
>when sum > total
>in your example, 10 checks vs 17 (depending how you count)

Read my posting more carefully. I do stop when the sum is too
big. It is just a matter of the order that the elements are
considered.

[snip]

[Al Marino]

my point was you can stop sooner on iterations
if sort ascending 2,5,7,8,14,16

2 +5 +7 +8 no more necessary
2 +5 +8 no more necessary
2 +5 +14 "
5 +7 +8 "
5 +7 +14 "
5 +8
7 +8

which is less checks than descending

"Gene Wirchenko" <ge...@ocis.net> wrote in message

news:cljt349jv50t9a06j...@4ax.com...

[Gene Wirchenko]

"Al Marino" <almarino_AT_intelliform.net> wrote:

>my point was you can stop sooner on iterations
>if sort ascending 2,5,7,8,14,16
>
>2 +5 +7 +8 no more necessary
>2 +5 +8 no more necessary

You actually have to consider the next item or do a calculation
to know this. If the result of the calculation is that the next item
might fit, then you then have to try the next item. I just try the
data item which is about the same complexity as the calculation.

>2 +5 +14 "
>5 +7 +8 "
>5 +7 +14 "
>5 +8
>7 +8
>
>which is less checks than descending

Ah, no. You are assuming things about the data that I am not. I
mention the data items considered. Here is ascending done my way.

Sorted Ascending: 2, 5, 7, 8, 14, 16

Run:

Pick 2.
Pick 5. Pick 7. Reject rest (8, 14, 16). Back off 7. Pick 8.
Reject rest. Back off 8. Reject rest. Back off 5.
Pick 7. Pick 8. Reject rest. Back off 8. Reject rest. Back off
7.
Pick 8. Reject rest. Back off 8.
Pick 14. Reject rest. Back off 14.
Pick 16. Reject rest. Back off 16. Back off 2.
Pick 5.
Pick 7. Pick 8. SOLUTION. Reject rest. Back off 8. Back off 7.
Pick 8. Pick 14. Reject rest. Back off 8.
Pick 14. Reject rest. Back off 14.
Pick 16. Reject rest. Back off 16. Back off 5.
Pick 7.
Pick 8. Reject rest. Back off 8. Reject rest. Back off 7.
Pick 8. Reject rest. Back off 8.
Pick 14. Reject rest. Back off 14.
Pick 16. Reject rest. Back off 16.

It is about the same amount of text.

[Al Marino]

Gene,
please excuse me, I am not trying to belabor the point.
This was an interesting problem and one of the few that is
actually a good use of recursion

I am only considering that they increase in value
your example,

>>2 +5 +7 +8 no more necessary
>>2 +5 +8 no more necessary
>
> You actually have to consider the next item or do a
> calculation
> to know this. If the result of the calculation is that
> the next item
> might fit, then you then have to try the next item. I
> just try the
> data item which is about the same complexity as the
> calculation.

you do not have to consider the next item since 2+5+8 is >
20 and all other 2+5+8 level must be greater than
there might be many such ( eg data 2,5,7,8,8,8,8,8,8,8,...)
so the next to check is 2 +5 +14 and then no more 2+5 level

al

"Gene Wirchenko" <ge...@ocis.net> wrote in message

news:tvc044d0q53m5m2g6...@4ax.com...