良問ですね。

鍋あり谷あり:[プログラミング]あなたならどうお書きになります1.0
クリスマスパーティーでプレゼント交換を行う。
  • 全員、誰かにプレゼントを一つあげ、誰かからプレゼントを一つもらう。
  • 参加者は、自分と同じグループに属している人にはプレゼントをあげない。
  • どのグループにも属さない人や、複数のグループに属する人はいない。
この条件を満たすようなプレゼント交換が等確率で出るような、プレゼント交換方法生成プログラムを実装せよ

以下、perlでの素直な実装。

use strict;
use warnings;

sub px {
    my $party = shift;
    my ( %from, %to );
    for my $to ( keys %$party ) {
        my $group = $party->{$to};
        my @candidates = grep { 
            $_ ne $to                   # not thyself
            and $party->{$_} ne $group  # not a member of thy group
            and !$from{$_}              # not received the present yet
        }  keys %$party;
        return unless @candidates;      # failure
        my $from = $candidates[ int( rand(@candidates) ) ];
        $to{$to}     = $from;
        $from{$from} = $to;
    }
    return \%to;
}

sub validate_party {
    my $party = shift;
    my %group;
    $group{ $party->{$_} }++ for keys %$party;
    my $total = scalar keys %$party;
    while ( my ( $g, $us ) = each %group ) {
        my $them = $total - $us;
        die "invalid party :", " group $g ($us) has more people",
          " than the total of the rest ($them)\n"
          if $us > $them;
    }
}
sub exchange_present{
    my $party = shift;
    validate_party($party);
    my $result;
    1 until $result = px($party);
    $result;
}

local $\ = "\n";
use Data::Dumper;
local $Data::Dumper::Terse = 1;
local $Data::Dumper::Indent = 0;

# my %party = map{ $_ => $_%5 } (0..99); # example of a large party
# my %party = ( foo => 'a', bar => 'b', quux => 'b' ); # invalid group
my %party = (
             dan    => 'parent',
             naomi  => 'parent',
             hazumi => 'child',
             kiwami => 'child',
            );

print Dumper exchange_present( \%party );

この問題、一目見ればわかりますが、解なしの場合が存在することがすぐ分かります。例えば、2名がグループA、1名がグループBの時は、必ずグループAの人が1名誰にもプレゼントを渡せなくなってしまいます。ここから解が存在する条件は、「すべてのグループにおいて、そのグループの人数がその他のグループの人数の合計以下であること」となります。上記のプログラムは、それもちゃんと実装しています。

Happy Holidays!

Dan the Party Animal