pythonのリストからランダムに、同じように考えられる組み合わせを生成する

Question

私はこのようなリストを持っているとしましょう：['a','b','c']。このリストから無作為に組み合わせる必要があります。例えば、['a','c']です。しかし、私はすべての組み合わせが等しい確率を持つようにする必要がありますので、['a']を得る機会は、['b','c']を得るチャンスとまったく同じでなければなりません。私の実際のリストは22要素で、すべての組み合わせを列挙することは不可能です。私の最初の考えはrandom.sampleを使用することでしたが、ランダムに選択する必要がある要素の数を指定する必要がありましたが、確率は（この組み合わせの要素の数）/（すべての組み合わせの要素の数）これは巨大な数字です。もっと良い方法はありますか？これは何千回も実行されるので、効率的なソリューションが評価されます。

Answer 1

これを行うには非常に効率的な方法があります。与えられたセットのすべての組み合わせのセットは、power setと呼ばれ、与えられたセットのすべてのサブセットのセットです。集合Sがm個の項目を含む場合、空集合とS自体を含めて合計で2**mの組み合わせが可能です。

Sのパワーセットからランダムに選択するには、range(2**m)の乱数nをパワーセットのインデックスとして選択し、nに対応する組み合わせを生成するだけです。

nのバイナリ展開を見て、インデックス番号nを組み合わせに変換できます。 nにはmビットがあります。これらのビットをSのアイテムとペアリングします。ビットが1の場合、そのアイテムが選択され、0の場合はそのアイテムが拒否されます。

ここで短いデモです。

from random import seed, randrange 

seed(42) 

def indexed_combination(seq, n): 
    result = [] 
    for u in seq: 
     if n & 1: 
      result.append(u) 
     n >>= 1 
     if not n: 
      break 
    return result 

print('Testing indexed_combination') 
seq = 'abc' 
for i in range(1 << len(seq)): 
    print(i, ''.join(indexed_combination(seq, i))) 
print() 

def random_combination(seq): 
    n = randrange(1 << len(seq)) 
    return indexed_combination(seq, n) 

print('Testing random_combination') 
seq = 'abcdefghij' 
for i in range(20): 
    print(i, random_combination(seq)) 

出力

Testing indexed_combination 
0 
1 a 
2 b 
3 ab 
4 c 
5 ac 
6 bc 
7 abc 

Testing random_combination 
0 ['c', 'f', 'g', 'h'] 
1 ['a', 'b', 'e', 'f'] 
2 ['a', 'b', 'e', 'f', 'j'] 
3 ['a', 'c', 'e', 'f', 'g', 'h', 'i'] 
4 ['a', 'd', 'g', 'h', 'i'] 
5 ['a', 'c', 'd', 'e', 'i'] 
6 ['a', 'e', 'g', 'h'] 
7 ['b', 'e', 'f', 'h'] 
8 ['f', 'g', 'i', 'j'] 
9 ['a', 'g'] 
10 ['a', 'c', 'd', 'e', 'f'] 
11 ['a', 'b', 'c', 'd', 'e', 'f', 'h'] 
12 ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i'] 
13 ['c', 'd', 'e', 'g', 'h', 'i'] 
14 ['b', 'c', 'e', 'f'] 
15 ['a', 'b', 'c', 'e', 'h', 'i'] 
16 ['a', 'b', 'd', 'e', 'g', 'i', 'j'] 
17 ['a', 'b', 'g', 'h', 'i'] 
18 ['a', 'b', 'c', 'e', 'h', 'i', 'j'] 
19 ['a', 'd', 'e', 'f', 'j'] 

---

Iは、固定されたシード番号とスクリプトの開始時にランダムseed関数を呼び出します。擬似乱数を使用するコードを開発するときは、乱数が再現可能なときにコードをテストしてデバッグするのが簡単になるため、これを行うと便利です。実際のアプリケーションでは、システムのエントロピーソースをラドマイザーに設定する必要があります。 seedコールを削除するか、seed(None)を実行して簡単に行うことができます。標準のMersenee Twisterジェネレータが提供するものよりもランダム性が必要な場合は、random.SystemRandomクラスを使用してシステムのランダムソースにフックすることができます。

Answer 2

combinationを使用して、nを選択するための繰り返し可能性を作成し、chainを使用して、i = 1〜nのすべての組み合わせを組み合わせます。組み合わせの合計数は2 ** n - 1になるので、0から2 ** n - 2までのランダムな整数を選択します。最後に、isliceを使用して、繰り返し可能な値からその値を抜き取ってください。

from itertools import islice, combinations, chain 
from string import ascii_uppercase 

def pickcomb(i): 
    n = len(i) 
    allcomb = chain(*(combinations(i, j) for j in range(1, n + 1))) 
    k = random.randint(0, 2 ** n - 2) 
    return list(islice(allcomb, k, k + 1))[0] 

pickcomb(ascii_uppercase[:22]) 

('A', 'E', 'F', 'H', 'I', 'K', 'L', 'M', 'O', 'Q', 'S', 'T') 

---

私は多数の上に、私たちはかなり均一な分布を見るべきであると思われるのは、

それをテストしてみましょう。 pandas.value_countsを使用します。正確な観測タイプ数とかなり均一な分布を持っていることが分かります。

import pandas as pd 

s = pd.value_counts([pickcomb(ascii_uppercase[:5]) for _ in range(100000)]) 
print(len(s), 2 ** 5 - 1, s, sep='\n\n') 

31 

31 

(A, B, C, D, E) 3329 
(A, D)    3320 
(C, D)    3301 
(A, D, E)   3277 
(D, E)    3276 
(B, C, D)   3270 
(A, E)    3268 
(A, B)    3258 
(C, E)    3251 
(A, B, C)   3250 
(A, B, C, E)  3248 
(C, D, E)   3245 
(A, C)    3245 
(D,)    3241 
(C,)    3234 
(A, B, D)   3227 
(A, C, E)   3220 
(B, D, E)   3215 
(A, B, E)   3213 
(B, C, E)   3213 
(B, C, D, E)  3213 
(A, C, D)   3211 
(B, E)    3194 
(B, C)    3193 
(A, B, D, E)  3185 
(A, B, C, D)  3174 
(A, C, D, E)  3158 
(E,)    3151 
(B,)    3150 
(B, D)    3148 
(A,)    3122 
dtype: int64