2

効率的に、置換なしでリストの一意のランダム順列が多数必要です。私の現在のアプローチ：

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]

whereget_nth_permutationは、まさにそのように聞こえますが、効率的です (O(N) を意味します)。ただし、これは に対してのみ機能しlen(population) <= 20ます。単純に 21! 驚くほど長いのでうまくいきxrange(math.factorial(21))ません:

OverflowError: Python int too large to convert to C long

O(N) で置換せずに k 個の一意の順列をサンプリングするより良いアルゴリズムはありますか?

4

5 に答える 5

6

ある時点までは、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)、 a を使用しsetて重複を記録し、それが懸念される場合はスキップします (ただし、にn近づくlen(l)!と失速します)。何かのようなもの：

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

しかし、乱数ジェネレーターの期間を超えてリストの可能な順列の数が増加するため、len(l)長くなるほど信頼性が低くなります! random.shuffleしたがって、すべての順列がlそのように生成できるわけではありません。その時点で、一連の乱数をマップする必要があるだけでなく、とget_nth_permutationの間のすべての乱数を生成できる乱数ジェネレーターも必要です。比較的均一に分布しています。そのためには、ランダム性のより堅牢なソースを見つける必要があるかもしれません。0len(l)

ただし、それがあれば、解決策はMark Ransomの答えと同じくらい簡単です。

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

これが問題になる正確な長さはどれくらいですか? わからない。しかし、価値があるのは、によって実装されているメルセンヌツイスターの周期randomは2**19937-1です。シャッフルのドキュメントでは、一般的な方法で私の主張を繰り返しています。ウィキペディアのこの問題に関するコメントも参照してください。

于 2012-04-19T17:05:32.470 に答える
4

使用する代わりに、xrange必要な数になるまで乱数を生成し続けます。a を使用するsetと、それらがすべて一意であることを確認できます。

permutation_indices = set()
while len(permutation_indices) < k:
    permutation_indices.add(random.randrange(total_permutations))
于 2012-04-19T16:37:24.367 に答える
1

nth_permutationの実装が1つあり（どこから入手したかはわかりません）、目的に合わせて変更しました。これはあなたのニーズに合うのに十分速いと思います

>>> 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)]
于 2012-04-19T16:53:38.290 に答える
0

itertools.islice代わりに使用できますxrange()：

CPython 実装の詳細: xrange() はシンプルで高速であることを目的としています。これを実現するために、実装によって制限が課される場合があります。Python の C 実装では、すべての引数がネイティブ C の long (「短い」Python 整数) に制限されており、要素の数がネイティブ C の long に収まる必要もあります。より広い範囲が必要な場合は、 itertools モジュールを使用して代替バージョンを作成できます: islice(count(start, step), (stop-start+step-1+2*(step<0))//step)。

于 2012-04-19T16:45:00.373 に答える
0

クヌース シャッフルを探しているようです。幸運を！

于 2012-04-19T16:25:03.800 に答える