getting all combinations 1

[557]

can someone tell me the logic to use for this problem

i have a table with about 1000 records. each record has many detail fields and an amount field. when the user gives a particular amount ,say 10000, i want to find all combinations of records in this table which will give me a sum of exactly this amount 10000. there may be 1 record or 2 records or 3 records or n records that give me this amount as sum. how do i get all the combinations in this table for this requirement?

 

[johnwm]

Sometimes 5 minutes of basic maths will save a few hours of programming (and a few millenia of processing time )

To give a quick comparison, the SETI project has around 5 million users, with a total processor time of over 2 million years. It has so far done around 6 x 10[sup]21[/sup] floating point calcs.

And we're looking for 10[sup]301[/sup] flops!

Nuff said I think!

________________________________________________________________
If you want to get the best response to a question, please check out FAQ222-2244 first

'If we're supposed to work in Hex, why have we only got A fingers?'

http://www.essexsteam.co.uk

for steam enthusiasts

 

[strongm]

An alternative to looking at all the permutations of the 1000 numbers, and rejecting those that don't make the grade would be to figure out all the ways that we can sum integers to the target value, and then seeing if we've got the necessary numbers

e.g we make 3

3
1+2
1+(1+1)
2+1
(1+1)+1

This is a much smaller problem space,

 

[PatrickIRL]

If it is a database table why can't you do a select statement first on the number the user has input and only look for numbers <= to that figure, this should also cut down the possibilities.

Patrick

 

[N1GHTEYES]

Is your data sorted? If so, you could start by adding all of the smallest numbers (starting with the smallest) until you reach a value greater than your required value.

The maximum number of "winning" combinations could then be calculated for the data set. If you have N items in total and the maximum number of items in the sum found above is M then your maximum number of possible combinations is (N)*(N-1)*(N-2).....(N-M). In practice it would probably be much smaller, but this is an upper limit.

At this point, you can do the calculation (of maximum possible combinations) and decide if it is worth going any further. If you do proceed, having the data sorted should also help there too.