Calculation/script to find a specific subset of records?

[amigotto]

I have a found set of just over 300 records. Each record has a value field and a summary field which shows the total value of all found records.

I need to find a combination or subset of these found records whose total value is equalled to a specific amount - let´s say $96.72.

Can I do this in Filemaker 7?

Thanks,

Alvise Migotto

[Wim Decorte]

Is it simply a matter of starting with the first record and looping through the records (adding their value to a subtotal) until the subtotal reaches 96.72?

Or is it more complex in that you need to find the exact combination of records out of these 300 whose summed values equal exactly 96.72?

[Søren Dyhr]

Can I do this in Filemaker 7?

If it's an exact combination is the answer: Probably, but it must be easier under FM8 when we have GetNth to our disposal.

But you should think carefully about the algoritm since trying ALL subsets is a looping thru 2,03703597633e+90 sets, they should be ordered/sorted and most significant bit is the number just below the value you wish to find the combination for. But even though will there be plenty of time to walk the dog or go jogging.

I'm afraid this isn't filemaker strongest point - number crunching. It's usually a task you perform on things like this:

http://developer.apple.com/hardware/hpc/xgrid_intro.html

--sd

[amigotto]

I need to find an exact combination, but:

1 - There may be more than one subset that results the exact total. This is OK, actually an ideal situation.

2 - There may also be NO subset that results in the exact total.

[amigotto]

Thanks. How would this work with GetNth (I have access to FM8)?

I usually do this by exporting to Excel and just switch numbers on/off until I reach the desired total. A little time consuming but usually not so bad. However, this time the numbers I must choose from inlclude few nice round numbers like 10.00, 30.00, 45.00 68.00, etc. They are mostly 36.13, 10.44, 73.74, etc.

I´m trying to find a solution with the Solver in Excel but no success yet. I just thought if there was a solution in Filemaker it´d make things much simpler, as I need to do this on a frequent basis.

[Søren Dyhr]

Alright I have given it a stab as a template, but this is not something computers as such can level real brainpower, there is worlds between to learn a child to make a jigsaw puzzels ...well it just takes encouragement and then to teach a robot to do the same. The child or even better a chartered accoundant have expirience and focus that not any kind of machinery can't compete with!

The biggest problem is that humans interact various algorithms at the same time - where we have to split them appart with computers.

But the topic as such is big big business ...large corporations can't have the touch and feel the small shop proprietar has as to which items should stand where in the shop to make the best sale ...such patterns is called datamining, and requires the strongest computing power availiable, this is usually done during the time the shop is closed.

In my first stab have I changed this CF slightly and used it with GetNth( but the algoritm does indeed still lack some power. I can't predict when rounding errors make Ronalds CF unreliable therefore have I only 10 records instead of your approximately 300.

--sd

plucking.zip

[amigotto]

Yes, that´s probably what makes it relatively easy to do in Excel by switching values on/off and making some substitutions manually to eventually find a correct subset. Even with this one of 300 values, I have gotten to within $0.01 of the target value with a little more time than usual. It just would be really handy to have this process automated so I can do other things!

I can only imagine that some years from now, when my grandson´s cell phone will be able to do this kind of stuff faster than you can say "HELLO?" while playing his favorite DVD in 3D hologram. On second thought...

Thanks for the file! I´ll have a look ASAP!

Cheers,

Alvise

[comment]

Very clever - using binary to switch values on and off to cycle thru all combinations. The custom function is not required - see attached. I have also added a step that eliminates records that are larger than the goal.

Still, I suspect that with that many records, this may be an excercise in futility. There are more efficient algorithms (google for "Knapsack problem"), but as things stand, you may have more time than to walk the dog. Perhaps even all the dogs in the universe.

LoopCombinations.fp7.zip

[amigotto]

My dog would be very happy!

Maybe I´m reading something wrong, but I believe the second file allows for multiple selections of a given value. I can only use one instance of a given value, unless another record (or records) has the same value.

Meanwhile, I´m doing the Google "Knapsack Problem" thing. My problem seems simpler than the standard knapsack problem which has more variables (just 1 on/off or 0/1 option), but the number of records to choose from to reach the "goal" makes it difficult.

I can get results with Excel´s Solver and with your FM8 file for smaller sets of records, so maybe spliting the found sets into smaller groups would be useful in some cases.

[comment]

I am sorry, I should have made this clear: my file is only a streamlining of Søren's; although I have eliminated the need for a custom function, it still uses the GetNthRecord() function, which is only available in version 8. I suppose I could replace even that by using a value list, but that would make it even slower, I think.

Yes, your problem is a bit simpler that the classic knapsack, but it is still very computation-intensive, as the number of combinations to check is doubled for every value in the list.

Edited February 8, 2006 by Guest

[amigotto]

Sorry! Yes it works in FM8.

Here´s an example that solved my immediate problem in Excel using a macro. I selected 18 of the 305 values and it found a combination that I could use - very fast.

Do you think this is possible in Filemaker?

recursion.zip

[Søren Dyhr]

Blast it's one of those macros that can't migrate into Open-Office. I'm almost dying get my hands on it to learn! But if it's exploiting something blackbox'ish aren't we any further.

What my hunch tells me is that M$ bought something in the vicinity of this:

http://www.solver.com/xlsengines.htm#Linear%20and%20Quadratic%20Programming%20Problems

--sd

[comment]

I can't see what the spreadsheet does either. Could you explain in a few words?

BTW, I timed 5 seconds to process 1024 iterations (10 numbers). Suppose you take a computer that is 5 times faster than mine. It will take 17 minutes to process 20 numbers, 12 days to process 30 numbers, and 34 years to process 40.

To process 100 numbers you'd need to wait around 40,000,000,000,000,000,000 years. Hmm... how long is that in dog years?

[Søren Dyhr]

Hmm... how long is that in dog years

Isn't it 7x ?? ...could talk about a long line of worn out's!

--sd

Edited February 8, 2006 by Guest

[amigotto]

Yeah I had the same problem with OpenOffice!

Here´s a link to the site where I found the file:

http://www.dicks-blog.com/archives/2005/10/27/which-numbers-sum-to-target/

It has the code so you can have a look, although I believe some of it doesn´t show up properly because of html translation.