鍋あり谷あり このページをアンテナに追加 RSSフィード

1904 | 06 | 07 | 09 | 10 |
1906 | 08 |
2004 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 03 | 05 | 06 | 08 | 09 | 11 | 12 |
2009 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 12 |
2010 | 01 | 09 | 10 |
2011 | 01 | 02 | 03 | 05 | 08 | 12 |
2012 | 12 |
2013 | 03 | 04 | 05 | 07 | 08 | 09 |
2014 | 01 | 02 | 05 | 08 |
2015 | 05 |
2016 | 05 | 07 | 08 |
<< 2006/12 >>
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31


2006年 12月 17日

[]あなたならどうお書きになります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

となる。参考までに。

539799