Ignoring the requirement from the other thread about not having duplicates in any of the groups,
If you re-read the other thread, the OP was concerned that no index was re-used. That is, whilst there are only 94 values, there are 186 indexes and each index should only be used once.
To simplify in the traditional way. There are 186 balls each with a number on that must be distributed into 31 boxes, 6 per box, such that the sums of the values on the balls in each box is between 840-900 inclusive.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] |
BrowserUk,
I am just now getting a chance to look at this. While I haven't had an opportunity to implement my heuristic algorithm outlined above, brute forcing it should be in the realm of possibility.
186 Choose 6 = 53,011,617,022
See Arbitrarily Nested Loops where I indicated I could get 25-30 million iterations per second using a modest windows machine (albeit in C). That makes checking all possible combinations in about 35 minutes. Of course, not all possible combinations need to be checked because every item you choose reduces the possible choices (can't undershoot or overshoot the target sum). I am a terrible C programmer and could not make a generic interface though ikegami gave it a go.
Since I don't really understand the OP's objective (I readily admit to having only skim read the original thread), I am not sure what approach to go with. My inclination would be a heuristic solution that almost always produces an acceptable solution though not always the best versus and exhaustive search that short circuits when it has found an acceptable solution or an exhaustive search that finds all possible acceptable solutions.
| [reply]
[d/l] |
brute forcing it should be in the realm of possibility. 186 Choose 6 = 53,011,617,022
Unfortunately, it's both less and more complicated than that.
(In the sample dataset), there are only 94 unique values; so 814,216,767 is very doable. It takes about 20 minutes in pure Perl to find the 142,138,770 complient groups of 6.
But then you have to come up with 31 of those sets of 6, where the 186 values, contained match the original 186.
Something like 814216767! / (814216767-31)! * 1 / 31!
Which I get to be something like: 2.07931e242. Somewhat too big to brute force.
Mind you, the OP only wanted one, not all of the solutions, so maybe it is still possible without heuristics. The trouble is, that he suggested that he wanted a different solution each time.
The problem with the heuristics offered so far, is that they are either determanistic and will find the same solution each time. Or non-determanistic and so might run for a very long time before finding one. Or worse. Some of them seemed to, more or less frequently, randomly choose starting positions from which their heuristics never find a solution.
I was working on an idea that encoded the complient 6of94 groups as bitstrings and saved each in 6 of 94 files according to the values contained. You then pick a file & mask at random; and use it to exclude files that contain values already in that mask--so if your first mask has the bit set for the 311 value, which can only appear once, you can immediately exclude all the masks in the 311 file. You then pick another file at random ANDing the masks with the original and rejecting collisions; Once you find a compatible mask, you OR it with the first; reject the files for any maxed out values ones, and repeat till you've selected 31 masks.
But the OP seemed to loose interest--or silently chose to go with one of the existing solutions--and I cracked a tooth.
Whilst waiting at the dentist, I was trying to distract myself by working out what the OPs purpose might be. And the best I could come up with was randomly (re)distributing variable size images or thumbnails onto a fixed width page (840-900 wide), on a grid 6 wide and 31 deep. That thought, the type of website such formatting is frequently done, the effort involved in coding the solution, and the toothache, meant I lost interest also.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l]
[select] |