in reply to Kris Kringle / Secret Santa

You would have better results by planning a whole set of years in advance. The problem is similar to, but simpler than the one here Lunch Bunch arrangement problem.

Suppose there were a constant group of 5 friends. The following block would set up a schedule for four years, such that each gives to each of the others without repeats. 

1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1

You would read down the columns, so that the first year person 1 gives to person 5, and the next year to person 4, and so on. You could most likely fit in old information into the pattern by appropriate assignment of numbers and rearrangements of rows.

All you need is a latin square of appropriate size to plan for any number of people.

Replies are listed 'Best First'.
Re: Re: Kris Kringle / Secret Santa
by BigLug (Chaplain) on Jan 10, 2004 at 07:22 UTC
    Yeah this is all very very easy: 
    my @names = qw/andy betty craig daniel edith/;
my %reverse_lookup;
@reverse_lookup{ @names } = (0..4);

foreach $year (2004 .. 2007) {
    foreach (sort keys %people) {
        printf("%04d: %s buys for %s\n", 
            $year, 
            $_, 
            $names[ ($year+$reverse_lookup{$_}) % 4 + 1]
        );
    }
}

    [download]
    However, the group isn't constant. My original data introduces nancy after two years, if we suddenly do this then a latin square doesn't work.

    Also, I must point out that there will be data such as sally can never buy for derek ... not after last years christmas party. So derek is on sally's list .. permanently. Even after we reset it at the end of the cycle.

[reply]
[d/l]
      I saw the addition of Nancy after two years in your original data, but I chose to ignore it because it makes a full solution impossible. Suppose we wanted to continue the pattern for the next four years. Andy, Betty, Craig, Daniel, and Edith each want to buy something for Nancy (and for the other three they have not bought for yet) before they go back to anyone earlier on their list. That's five buyers for Nancy in four years, which won't work.

      I think the best you can do when a new person is added is to compute a new latin square from that point and try to place the previous pairings as low in the square as you can.

      I also think I could prove that having one person who cannot buy for another also makes a full cycle impossible. In that case, you could place that pairing on the last line of the latin square, and start a new square when you get to that point.

[reply]

In Section Seekers of Perl Wisdom