Combinatorics problem. (Updated with more info.)by BrowserUk (Patriarch)
|on Dec 11, 2015 at 06:47 UTC||Need Help??|
BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:
Given a number of postcards (say 5) and a number of pigeon holes (say 3); how many ways are there to distribute the cards into the holes such that each hole contains at least 1?
For the 5/3 case above, the following possibilities exist:
How to efficiently generate that sequence? The order of generation is immaterial.
Update: Need a better way
One way to do it, is to filter Algorithm::Combionatorics::variations_with_repetition() for the sum of values.
Ie. Generate the 27 variations:
And then filter on the sum() of the subsets to reduce it to the 6 I need:
Which doesn't seem too bad until you consider a realistic set, rather than my simple example.
For instance, with 12 postcards and 7 pigeon holes, there are 35,831,808 variations_with_repetition() each of which must be summed and compared in order to discard 99.9% to arrive at the 462 I need. That's horribly inefficient :(
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
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". I knew I was on the right track :)
In the absence of evidence, opinion is indistinguishable from prejudice.