今年もうちでクリスマスパーティーをやる。
クリスマスパーティーにはプレゼント交換。
で、誰が誰にプレゼントを渡すのかを決めるわけだが、人間がサイコロなどで乱数をつくって決めるのは、実は難しい。
そこで今日の出題。
クリスマスパーティーでプレゼント交換を行う。
- 全員、誰かにプレゼントを一つあげ、誰かからプレゼントを一つもらう。
- 参加者は、自分と同じグループに属している人にはプレゼントをあげない。
- どのグループにも属さない人や、複数のグループに属する人はいない。
この条件を満たすようなプレゼント交換が等確率で出るような、プレゼント交換方法生成プログラムを実装せよ
わかりにくいと思うので、グループについて解説。
例えば。私と杏子と穴田さんと出部さんの四人で行うとする。私と杏子は「鍋谷夫妻」というグループに属しており、穴田さんは「穴田さん」というグループ、出部さんは「出部さん」というグループに属している。と考える。
これによって、私が杏子にプレゼントをあげたり、杏子からプレゼントをもらったりすることを避けることが出来る。自分へのプレゼント禁止ルールも含んでるし。
それと等確率。
例えば上記の例だと4通りあるわけだが、その4通りが等確率に出ればいい。
必要があっての問題なので、きっと matz さんから「現実から乖離している」とは言われないと思うがどうだろう。でかくもないし、汁もしたたってないけど。
あ。締め切りは 24日ということで。
12/20追記
クリスマスパーティーのプレゼント交換は、交換という言葉があたっているものの、あげた人からもらうとは限らない。
例えば。
a1, a2 がグループa。それ以外は自分自身のみを含むグループに属しているとする。
4人・5人の場合は以下のようになる。（x→y は、x は y にプレゼントをあげる、という意味）
a1, a2, b, c の4人の場合、以下の4通り:
a1→b, a2→c, b→a1, c→a2
a1→b, a2→c, b→a2, c→a1
a1→c, a2→b, b→a1, c→a2
a1→c, a2→b, b→a2, c→a1
a1, a2, b, c, d の5人の場合、以下の24通り:
a1→ b, a2→ c, b→ d, c→a1, d→a2
a1→ b, a2→ c, b→ d, c→a2, d→a1
a1→ b, a2→ c, b→a1, c→ d, d→a2
a1→ b, a2→ c, b→a2, c→ d, d→a1
a1→ b, a2→ d, b→ c, c→a1, d→a2
a1→ b, a2→ d, b→ c, c→a2, d→a1
a1→ b, a2→ d, b→a1, c→a2, d→ c
a1→ b, a2→ d, b→a2, c→a1, d→ c
a1→ c, a2→ b, b→ d, c→a1, d→a2
a1→ c, a2→ b, b→ d, c→a2, d→a1
a1→ c, a2→ b, b→a1, c→ d, d→a2
a1→ c, a2→ b, b→a2, c→ d, d→a1
a1→ c, a2→ d, b→a1, c→ b, d→a2
a1→ c, a2→ d, b→a1, c→a2, d→ b
a1→ c, a2→ d, b→a2, c→ b, d→a1
a1→ c, a2→ d, b→a2, c→a1, d→ b
a1→ d, a2→ b, b→ c, c→a1, d→a2
a1→ d, a2→ b, b→ c, c→a2, d→a1
a1→ d, a2→ b, b→a1, c→a2, d→ c
a1→ d, a2→ b, b→a2, c→a1, d→ c
a1→ d, a2→ c, b→a1, c→ b, d→a2
a1→ d, a2→ c, b→a1, c→a2, d→ b
a1→ d, a2→ c, b→a2, c→ b, d→a1
a1→ d, a2→ c, b→a2, c→a1, d→ b
となる。参考までに。
