O（N）で置き換えのないk個のランダム置換の例

Question

リストを置換せずに多数の一意のランダム置換を効率的に行う必要があります。私の現在のアプローチ：

get_nth_permutationが効率的に（O（N）を意味する）、それはのように聞こえるまさにん

total_permutations = math.factorial(len(population)) 
permutation_indices = random.sample(xrange(total_permutations), k) 
k_permutations = [get_nth_permutation(population, x) for x in permutation_indices] 

。ただし、これはlen(population) <= 20の場合にのみ有効です。 xrange(math.factorial(21))が動作しないようにmindblowingly長いです：

OverflowError: Python int too large to convert to C long 

はO（N）で交換することなく、独自の順列をk個サンプリングするより良いアルゴリズムがありますか？

Answer 1

xrangeの代わりに、必要な数だけ乱数を生成してください。 setを使用すると、すべてが一意であることが確認されます。

permutation_indices = set() 
while len(permutation_indices) < k: 
    permutation_indices.add(random.randrange(total_permutations)) 

Answer 2

あなたはKnuth Shuffleを探しているようです！がんばろう！

Answer 3

かわりxrange()のitertools.isliceを使用することができます。

CPython implementation detail: xrange() is intended to be simple and fast Implementations may impose restrictions to achieve this. The C implementation of Python restricts all arguments to native C longs (“short” Python integers), and also requires that the number of elements fit in a native C long. If a larger range is needed, an alternate version can be crafted using the itertools module: islice(count(start, step), (stop-start+step-1+2*(step<0))//step).

Answer 4

私は私があなたの目的のために変更された（私はそれを得たところからわからない）nth_permutationの一の実装を持っていました。私は、これは、ある時点まであなたの必要性

>>> def get_nth_permutation(population): 
    total_permutations = math.factorial(len(population)) 

    while True: 
     temp_population = population[:] 
     n = random.randint(1,total_permutations) 
     size = len(temp_population) 
     def generate(s,n,population): 
      for x in range(s-1,-1,-1): 
       fact = math.factorial(x) 
       d = n/fact 
       n -= d * fact 
       yield temp_population[d] 
       temp_population.pop(d) 
     next_perm = generate(size,n,population) 
     yield [e for e in next_perm] 


>>> nth_perm = get_nth_permutation(range(21)) 
>>> [next(nth_perm) for k in range(1,10)] 

Answer 5

に合わせて十分速いだろう、それは順列を取得するためにget_nth_permutationを使用することが不要だと考えています。リストをシャッフルしてください！

>>> import random 
>>> l = range(21) 
>>> def random_permutations(l, n): 
...  while n: 
...   random.shuffle(l) 
...   yield list(l) 
...   n -= 1 
... 
>>> list(random_permutations(l, 5)) 
[[11, 19, 6, 10, 0, 3, 12, 7, 8, 16, 15, 5, 14, 9, 20, 2, 1, 13, 17, 18, 4], 
[14, 8, 12, 3, 5, 20, 19, 13, 6, 18, 9, 16, 2, 10, 4, 1, 17, 15, 0, 7, 11], 
[7, 20, 3, 8, 18, 17, 4, 11, 15, 6, 16, 1, 14, 0, 13, 5, 10, 9, 2, 19, 12], 
[10, 14, 5, 17, 8, 15, 13, 0, 3, 16, 20, 18, 19, 11, 2, 9, 6, 12, 7, 4, 1], 
[1, 13, 15, 18, 16, 6, 19, 8, 11, 12, 10, 20, 3, 4, 17, 0, 9, 5, 2, 7, 14]] 

オッズはlen(l)> 15とn < 100000のため、このリストに表示されて重複に対して圧倒的ですが、あなたが、またはlen(l)の低い値のための保証が必要な場合は、ちょうどそれはだ場合は、重複を記録し、スキップするsetを使用しますあなたのコメントで見てきたように、nがlen(l)!に近づくと、これはストールします。ような何か：len(l)が長くなると、もはやとして、リストの可能な順列の数は、乱数ジェネレータの期間を超えて増加するため

def random_permutations(l, n):  
    pset = set() 
    while len(pset) < n: 
     random.shuffle(l) 
     pset.add(tuple(l)) 
    return pset 

はしかし、random.shuffleは、信頼性の低いなります！だから、lのすべての順列をそのように生成することはできません。その時点で、get_nth_permutationを一連の乱数にマップするだけでなく、すべての乱数を0とlen(l)の間で生成できる乱数ジェネレータも必要です。比較的均一な分布である。それは、より堅牢なランダム性の源を見つける必要があるかもしれません。

しかし、いったんそれができたら、解答はMark Ransomの答えと同じくらい簡単です。

len(l)でrandom.shuffleが信頼できない理由を理解するには、次の点を考慮してください。 random.shuffleは、0とlen(l) - 1の間の乱数を選択するだけです。しかし、それはその内部状態に基づいてそれらの番号を選び出し、有限（そして固定）の状態数しか取ることができません。同様に、渡すことができる可能なシード値の数は有限です。これは、生成することができる固有の一連の数列も有限であることを意味します。 sと設定してください。 len(l)! > len(s)の場合、これらの順列に対応するシーケンスはsにないため、一部の順列は決して生成できません。

これが問題になる正確なの長さは何ですか？よく分かりません。しかし、価値があるものについては、randomで実装されているメルセンヌツイスタの期間は2**19937-1です。 shuffle docsは一般的な意味で私の意見を繰り返します。 Wikipediaの問題については、hereで何を言いたいのかも見てください。