ランダムだと！？！？(ガタッ - 西尾泰和のはてなダイアリー

確かに、このテンプレには僕も飽きている：

onk:「リンゴが10個あります。ランダムに3人で取り分けなさい」ってどうコードに落とすと綺麗かな。。
yoshiori: @onk ランダムだと！？！？
onk: @yoshiori 擬似ランダムでいいです
yoshiori: @onk ふう、焦らせやがって……(俺の中でここまでテンプレ)
yoshiori: もう、「ランダム」という言葉に反応してしまうのはネタでも良くない気がしてきた

そこで新しいマサカリを考えてみた。「お前はなにを等確率にしたいんだ！？！？」

2個のりんごをAさんとBさんの2人に配ることを考えてみよう。全部で4通りの配り方がある。(A, A), (A, B), (B, A), (B, B)の4つだ。

この4通りを等確率にしたいのならば、それぞれのりんごについて1/2の確率でAとBに振り分ければ良い。ちなみにPythonのrandom.choiceは与えられた要素の一つを選ぶ関数だ。

>>> from random import choice
>>> [choice("AB") for i in range(2)]
['B', 'A', 'A', 'A', 'B', 'B', 'C', 'C', 'B', 'A']

つまり10個を3人に配るならこうだ。

>>> [choice("ABC") for i in range(10)]
['B', 'A', 'A', 'A', 'B', 'B', 'C', 'C', 'B', 'A']

これでお前は満足なのか？違う？

「そうじゃない！(A, B)と(B, A)は区別したくないんだ」

そうか、(A, B)と(B, A)は両方「Aに1個、Bに1個」として同一視したいのか。ならば全部で3通りの配り方がある。(2, 0), (1, 1), (0, 2)の3つだ。

この3通りを等確率にしたいのならば、これでいい。

>>> from random import random
>>> a = int(random() * 3)
>>> b = 2 - a

でも、この方法は「2つに分ける」時にしか使えない。10個を3人で分けるならこうかな？

N = 10
def sampling():
    x = int(random() * (N + 2))
    y = int(random() * (N + 1))
    if x > y:
        x, y = y, x - 1
    return (x, y - x, N - y)

このコードでは「10個のりんごを3人で分ける」を「りんごを横一列に並べて、りんごの左右11箇所のスペースのうち2箇所(x, y)についたてをおき、xより左がAさんの、xとyの間がBさんの、yより右がCさんのとする」と読み替えている。で「x <= y」という条件付きでxとyをサンプリングしないといけないんだけど、条件を満たさないものを捨てるのがもったいないので回転して再利用している。

確認してみよう。660000回サンプリングしてみると、66パターンの出力がみんな大体10000回ずつ出てくることがわかる。

>>> from collections import Counter
>>> Counter(sampling() for _x in xrange(660000))
Counter({(9, 0, 1): 10179, (3, 1, 6): 10161, (1, 9, 0): 10135, (0, 6, 4): 10132, (2, 0, 8): 10131, (3, 7, 0): 10119, (6, 1, 3): 10117, (1, 6, 3): 10112, (0, 7, 3): 10098, (7, 2, 1): 10096, (7, 1, 2): 10083, (10, 0, 0): 10083, (2, 6, 2): 10076, (1, 7, 2): 10068, (7, 0, 3): 10057, (4, 1, 5): 10054, (9, 1, 0): 10050, (2, 7, 1): 10043, (3, 4, 3): 10043, (5, 1, 4): 10041, (2, 5, 3): 10041, (0, 8, 2): 10040, (6, 3, 1): 10040, (1, 0, 9): 10039, (2, 8, 0): 10035, (4, 6, 0): 10033, (3, 3, 4): 10030, (8, 1, 1): 10022, (4, 5, 1): 10020, (5, 0, 5): 10018, (6, 4, 0): 10014, (5, 2, 3): 10011, (6, 2, 2): 10009, (4, 2, 4): 10008, (8, 0, 2): 10005, (3, 6, 1): 9996, (0, 2, 8): 9990, (0, 1, 9): 9983, (2, 1, 7): 9980, (2, 3, 5): 9979, (0, 9, 1): 9978, (1, 4, 5): 9973, (8, 2, 0): 9966, (0, 10, 0): 9964, (1, 1, 8): 9963, (3, 5, 2): 9958, (1, 3, 6): 9956, (7, 3, 0): 9949, (1, 5, 4): 9944, (3, 2, 5): 9943, (0, 0, 10): 9938, (4, 3, 3): 9938, (1, 8, 1): 9937, (5, 3, 2): 9918, (4, 0, 6): 9917, (1, 2, 7): 9910, (2, 4, 4): 9909, (4, 4, 2): 9895, (5, 5, 0): 9887, (3, 0, 7): 9886, (0, 5, 5): 9880, (5, 4, 1): 9854, (6, 0, 4): 9852, (0, 3, 7): 9851, (0, 4, 6): 9846, (2, 2, 6): 9817})

一般にM人に分ける場合にどうするかはよくわからない。広めにサンプリングして、x1 <= x2 <= ... <= x_(M-1) の条件を満たさない場合は捨ててやりなおす方法(棄却サンプリング)でとりあえず可能だろうけど、Mが大きくなるとどんどん効率が悪化する。「ソートして差をとる」というディリクレ分布からのサンプリングで使われる方法が使えないかと思ったが、今回のケースでは「x = yになる確率」が0じゃないので使えない。

ぜーはーぜーはー(吐息) お前の求めていたものはこれか？なに、違う？

「(0, 2)と(2, 0)は区別したくない」

先に言え…。そういう分け方を希望するなら、2個を2人に分ける場合、全部で2通りの分け方がある。(2, 0), (1, 1)の2つだ。

めんどくさくなってきたのでこれでいいですか：

>>> choice(((2, 0), (1, 1)))
(2, 0)

取りうる値のパターンが十分小さいなら、列挙して選択するのが一番手っ取り早い。10個を3人に分ける分け方は全部で14通りだから、列挙で十分。(っていうかさっきのも66通りだったから面倒くさいこと考えないで列挙したら良かったんじゃね？)

14個なら手で書きだしてもいいと思うけど、人間は間違える生き物だからコードで確認しておこう。permsにはさっき660000回サンプリングしてカウントしたCounterが入っていると思ってね。各値を昇順に並べ直し(sorted)たtupleにして、集合型setにつっこんでいる。手で求めた結果と同じく14個だった。

>>> perms.keys()
[(3, 0, 7), (1, 6, 3), (2, 8, 0), (2, 1, 7), (3, 7, 0), (3, 3, 4), (1, 0, 9), (2, 2, 6), (0, 8, 2), (5, 4, 1), (6, 0, 4), (5, 1, 4), (7, 1, 2), (1, 9, 0), (4, 3, 3), (5, 3, 2), (4, 2, 4), (5, 5, 0), (3, 5, 2), (7, 2, 1), (8, 0, 2), (2, 0, 8), (1, 7, 2), (5, 2, 3), (4, 1, 5), (7, 0, 3), (1, 1, 8), (5, 0, 5), (6, 4, 0), (0, 7, 3), (6, 1, 3), (6, 2, 2), (0, 1, 9), (4, 5, 1), (2, 4, 4), (4, 0, 6), (2, 5, 3), (2, 6, 2), (0, 6, 4), (0, 9, 1), (9, 1, 0), (1, 4, 5), (8, 1, 1), (3, 4, 3), (3, 1, 6), (1, 8, 1), (4, 6, 0), (0, 2, 8), (0, 3, 7), (2, 3, 5), (1, 5, 4), (3, 6, 1), (0, 5, 5), (9, 0, 1), (1, 3, 6), (1, 2, 7), (2, 7, 1), (7, 3, 0), (0, 0, 10), (6, 3, 1), (0, 10, 0), (8, 2, 0), (4, 4, 2), (3, 2, 5), (0, 4, 6), (10, 0, 0)]
>>> keys = _
>>> set(tuple(sorted(k)) for k in keys)
set([(2, 3, 5), (0, 0, 10), (0, 5, 5), (0, 4, 6), (1, 3, 6), (1, 2, 7), (2, 2, 6), (1, 4, 5), (2, 4, 4), (3, 3, 4), (0, 1, 9), (1, 1, 8), (0, 2, 8), (0, 3, 7)])
>>> combs = _
>>> len(combs)
14

というわけでここからのサンプリングはこんな感じ。Pythonの都合でsetからはchoiceできないのでtupleにしている。

>>> combs = tuple(combs)
>>> choice(combs)
(0, 0, 10)
>>> choice(combs)
(1, 4, 5)

ふー、一般にN個のりんごをM人に配る場合で、NやMが大きくて全パターン列挙が無理な場合にどうすればいいのかよくわからない。誰か教えて。

まとめ

「ランダムに」って手軽に言うけど、何を等確率にしたいのか決めなきゃ何もできないよ。