鍋あり谷あり

■[プログラミング]あなたならどうお書きになります1.0

今年もうちでクリスマスパーティーをやる。

クリスマスパーティーにはプレゼント交換。

で、誰が誰にプレゼントを渡すのかを決めるわけだが、人間がサイコロなどで乱数をつくって決めるのは、実は難しい。

そこで今日の出題。

クリスマスパーティーでプレゼント交換を行う。

• 全員、誰かにプレゼントを一つあげ、誰かからプレゼントを一つもらう。
• 参加者は、自分と同じグループに属している人にはプレゼントをあげない。
• どのグループにも属さない人や、複数のグループに属する人はいない。

この条件を満たすようなプレゼント交換が等確率で出るような、プレゼント交換方法生成プログラムを実装せよ

わかりにくいと思うので、グループについて解説。

例えば。私と杏子と穴田さんと出部さんの四人で行うとする。私と杏子は「鍋谷夫妻」というグループに属しており、穴田さんは「穴田さん」というグループ、出部さんは「出部さん」というグループに属している。と考える。

これによって、私が杏子にプレゼントをあげたり、杏子からプレゼントをもらったりすることを避けることが出来る。自分へのプレゼント禁止ルールも含んでるし。

それと等確率。

例えば上記の例だと4通りあるわけだが、その4通りが等確率に出ればいい。

手元では実装済みで、ruby で空行含めて 40行弱。

必要があっての問題なので、きっと 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

となる。参考までに。

Permalink | コメント(0) | トラックバック(0)