A programming question maybe!

[Peegee]

Or excel works too, but you would have to hand hold me with excel.

Pretend for argument's sake I'm an idiot who only can program in C

good luck!

In today's episode, PG receives a call from a client. The client was debited $5,278.53 (eg) out of their bank account and does not know what payments break down this total.

The good thing is that I or the client can pull up a list of transactions that went out on that day.

eg:
2859.34
128.33
483.44
592.22
1820.00
500.00
719.19
1400.00
300.00

(so the transactions that add up to the figure needed are: 2859.34, 300, 1400, 719.19)

How would I go about programming this? This is how I would start -

1) go down the list and grab the line as a variable
2) is the variable > the figure sought y ? if yes skip
3) now i have variable x which is < y
4) go down the list. is x2 > y-x1 ? if yes skip
5) if no, is x2 = y-x1? if yes finish return x1 and x2 (how?)
6) if no, store x1 and x2 somewhere. x1 = x1+x2
continue

but this only checks whether 2 numbers add up to y. Since there could be potentially infinite numbers, I am open to using an array that does not have a set amount of variables (but something like 50 would be fine lol I am not going to read out that many numbers to a client when i could be charging them 100s of dollars in service fees by saying 'nope.avi' )

Does this make sense? I feel like people who haven't quit programming for 13 years (sorry) are having an aneurysm reading this.

edit: lol yes there can be more than one solution. is this question too complicated to solve?

I found this online - read this for more discussion - http://www.mrexcel.com/pc09.shtml

[Endless]

How long is your transaction list ? <10? <50? <100? More?
Do you want to code it from the ground up or use a third party program (open source, ho!)?

[o_O]

This is a combinatorial problem. Basically, you want to be generating a list of all possible distinct combinations of numbers from your list. That is to say:

Lets say you have five transactions in an array ([] is standard notation for an array):
[10, 20, 30, 40, 50]

You want to find all possible combinations of transactions from this list, and sum each combination. To do that, you need to loop through your transaction list, choosing R items from your list of N transactions (aka your "alphabet"). For R = 2, you'll have the following list:
10, 20
10, 30
10, 40
10, 50
20, 30
20, 40
20, 50
30, 40
30, 50
40, 50


NOTE - The formula to calculate the total number of combinations is:
n!/(r!(n-r)!)
So it should be immediately obvious that as N and R increase, the number of combinations can get extremely big, extremely quick.

On to the algorithm...
1. First you want to begin selecting elements from the set. Since you don't know how many elements you're going to require to form your total, you should begin with a selection R = 1, working your way up to R = N. The smaller R is, the less expensive the computation, so that's why we begin at R = 1.

2. Next, you have to add R elements to a new set and calculate the sum, halting the program if you encounter your target number. I personally would choose recursion for an N < 100 and R < 20 or so, otherwise I'd choose an iterative approach. Explaining recursion and iteration is too big of a task to accomplish in one post, but there's a wealth of information on the internet about it.

However, here's a quick and dirty example in Ruby, which is super helpful and natively provides the Array#combination instance method, which generates all possible combinations for us:

<li># the silly arithmetic on line 4 is to round off the float error in ruby 1.8 and lower</li><ol><li>values = [2859.34, 128.33, 483.44, 592.22, 1820.00, 500.00, 719.19, 1400.00, 300.00]</li>
<li>target = 5278.53</li>
<li>1.upto(values.size) { |n|</li>
<li>	values.combination(n) { |c|</li>
<li>		p c if (100*c.reduce(:+)).round.to_f/100 == (100*target).round.to_f/100</li>
<li>	}</li>
<li>}</li></ol>

[Peegee]

Thanks mike; I had all but forgotten about this post. Now i have to go find ruby and dink around in this a bit :P

[Hollycat]

PGies is it ok if I send you the email adress of a friend of mine who is a doctoral computer engineering student?

[Endless]

Blerg, I hate being ignored, especially when the topic is so damn close to my Ph.D thesis.

At any rate, what you DON'T want is to generate the list of all possible combinations, because most likely, a lot of them are flat out undoable. Similarly, there's no point checking all combinations of elements of size up to N, since unless the average of the transactions is exactly total/N, you'll never use all N transactions. In fact, to calculate the absolute most you'll need, order the transactions in growing order, and sum until you reach or pass the total and count how many you needed. You could even do that at each step of your algorithm to know how many more max you'd need.

Anyway, your problem is pretty much the sum of subset problem (or subset sum problem). Traditionally, it uses integer values for the set values and total, but going from prices to integers is trivial (multiply x100, tada), and there are known best algorithms.

In C, one such algorithm is given here: Sum of subset problem in C (with a nice explanation to boot)
Basically, the idea is to recursively solve the problem for total-selected using the list of transactions with selected removed from it.
In Java, one could use this: How to implement the Sum of Subsets problem in Java - Stack Overflow (the last reply)

Aditionally, without any knowledge of algorithms, this kind of problem can be "easily" solved using binary/integer resolution programs, such as https://projects.coin-or.org/Cbc (open-source, freeware) or Cplex (proprietary, expensive) by modeling the problem correctly, feeding it to the program, then having it work the branching magic for you.

[Peegee]

Sorry
i'm reading the links you posted nao
/cries.