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:
3 1 1 2 2 1 2 1 2 1 2 2 1 1 3 1 3 1 // added per GrandFather's post below
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:
1 1 3 1 2 2 1 3 1 2 1 2 2 2 1 3 1 1
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 :(