On 2002-08-18 02:48, Chris Davison wrote:
Jay,
just a lateral thought :
we could reduce those 200 years down to a single year *if* we were able to incorporate into the code a method for splitting up the search into 200 different spreadhseets, sent to 200 volunteers, or a month if you split it down amongst 4,000
(not practical for accounts departments, yes, but let's forget abotu that, we're just interested in finding the solutions)
how easy would it be to slice the search up into 4,000 manageable segments - each segment being the next set to be searched when the spreadsheet was next copied and ran ?
surely it's possible to do this and then have the code email it's particular segment set of solutions back to the original person or project leader
[I'd been thinking about this along the lines of the SETI project where rather than have a single computer trying to analyse zillions of bits of info : packets of info are farmed out to volunteers across the world who each analyse their own little segment then post their results back]
I'm not saying we *need* 4,000 volunteers, what we need is the code that could do this.....
I don't know much about arrays in VBA, but know a simple way to allocate ranges of permutations based on their "binary address" (for want of a better way to describe it).... this would allow a block of 10,000,000 combinations to be checked easily
but if we could get the next version of the spreadhseet to check the next 10,000,000 combos, etc etc, that would work.....
any thoughts anyone ? it's way beyond my VBA skills right now
Chris
Hi Chris,
The partitioning of the problem will work, but that won't really help unless somebody comes up with a way to break Combin(53,12), for instance, into smaller parts.
C(53,1...7) shouldn't take too long, but the cap at 21 would take an enormous amount of time using a brute force approach.
After taking a closer look at the problem and writing a routine that will at least give me a benchmark, I am now more than ever convinced that the optimal non-Solver approaches are those of Ionnis and Sharad K., although we'll have to wait until Ioannis posts the routine.
Sharad and Ioannis are on the right track for large data sets....
Suppose that we find a solution 1,2,3,4,5 when selecting 5 items. Any future paths should ideally eliminate that path from the run.
What I am referring to here is that when you are searching for solutions of 6 numbers, you should never even get to
1,2,3,4,5,6
or
1,2,3,4,5,7 and so forth.
When you carry this out further, that entire solution path removes a ton of unnecessary searches.
I haven't quite figured out how Sharad's recersion works, but that approach seems to work really well. It appears that the routine starts with a pivot and exhausts the solutions for that single entry. Then, it removes the number from the set and continues. Over time, the original set of 54 is reduced, which really speeds things up.
Currently, all I have is an incomplete iteration method. The recursion routine I already posted goes through the combinations 3 times (!!!!!), so it is unworkable. My current thinking is along the lines of Sharad K.'s and also using multidimensional arrays to visualize the solution paths. That is still only a concept right now with no implementation.
OK, anybody up for any side bets on the winner? We've yet to hear from Damon Ostrander (my $$$ is on him if he jumps in
). Sharad and Ioannis are at the top right now. Mark W. and the Solver routines have to be considered top contenders, too. Jeffrey Chin's random search is along the lines of Tim C.'s first post in the newsgroup thread that started it all. Tim C. has some reservations about this, though.
We still don't know if others have already offered great stuff privately.
Of additional interest, especially with the Solver-type solutions, check out the following thread
http://groups.google.com/groups?hl=...008e.0202121923.69589444%40posting.google.com
Dana DeLouis, a MS MVP, is terrific with the Solver and Harlan Grove makes some nice posts about this problem type.
_________________
Bye,
Jay
EDIT: Forgot to add some reservations about the "winning" entry -- the processing power needed to exhaustively search all the combinations is beyond the scale of anything but a distributed computer system or a supercomputer, so if anybody comes up with a guarantee that all the answers are available within a few hours, I will be a bit disbelieving.
Also, to solve for 1 or 2 chosen at a time (or 52 or 53) doesn't require any VBA. 1 is obvious. For two, type the values in column A (starting at a1). Name this range DataRange or such. In C1, type the target value and name the cell GoalValue.
in B1, enter the following
=MATCH(ROUND(GoalValue-A1,2),DataRange,0)
and copy down the list. Any non-error values will indicate the row of a matched pair. Duplicates might mess this a bit, but this is relatively easy to get the case of n choose 2.
This message was edited by Jay Petrulis on 2002-08-20 12:57 
