=for advent_year 2007 =for advent_day 00 =for advent_title Choosing the perfect Secret Santa =for advent_author David Westbrook Some of Santa's Reindeer are gathering for a little holiday party, and wish to do I for gift-giving, where everyone is assigned each to another to bring a gift. This can be assigned by drawing a name from a hat, and keeping it if it's someone else, and replacing it if you draw yourself. But Comet and Cupid give each other gifts all the time, and last year Donner gave to Dancer, so those shouldn't occur this year. Which means that the list has to really be checked twice & thrice, also to make sure that no one is left out or doubled up. M, with some F assistance, will give us all the possible combinations to check for one that works. The approach is make an NxN grid represented by a 1-D array C<0..N*N-1>, and the solution (if any) will be one of the C combinations. So we'll get a random one of those, test it, and repeat until we find one or run out. Actually, it's (N*N-N-X) choose N, since the diagonal of the NxN, which is N elements, can immediately be excluded, as can any other (X of them) exclusions provided by the user. So for N=6, it's a 6x6 grid, with 36 elements 0-35, from 27 (36 minus 6 diagonals minus 3 exceptions) of which we'll choose 6. Those 9 exclusions are shown with strike-through in the grid below. Now C up the initial order of those 27, and then use F to start iterating through the combinations with the C method. Once a combination passes all the checks, we have all our I (indicated by yellow in the grid) and display them in the output.
 012345
 0 012345
167891011
2121314151617
3181920212223
4242526272829
5303132333435
=begin pre There are C(27,6) = 296010 total combinations. Tried 13074 combinations. Dasher => Comet Dancer => Cupid Comet => Dancer Cupid => Donner Donner => Blitzen Blitzen => Dasher =end pre
=sourcedcode modMC.pl