3

私は多数の整数順列を扱っています。各順列の要素数は K です。要素サイズは 1 バイトです。N 個の一意のランダム順列を生成する必要があります。
制約: K <= 144、N <= 1,000,000。

次の簡単なアルゴリズムを思いつきました。

  1. N 個のランダム順列のリストを生成します。すべての順列を RAM に保存します。
  2. リストを並べ替え、すべての重複を削除します (存在する場合)。重複の数は比較的少なくなります。
  3. 重複があった場合は、順列が N 個になるまでランダムな順列をリストに追加し、手順 2 に戻ります。

これを行うより良い方法はありますか？特に、すべての順列を RAM に保存しない (生成中にディスクに書き込む) 方法はありますか?

編集：最後に、生成された順列に順次アクセスする必要があります（1つずつ、ランダムアクセスの必要はありません）。RAM はより重要な要素です (すべての順列を一度に RAM に保存したくありません)。

4

4 に答える 4

6

考えられる解決策の 1 つは、ブルーム フィルターを使用することです。

順列をディスクに保存し (順番に書き込みます)、ブルーム フィルターを RAM に保持します。
順列を生成したら、それがブルーム フィルターに存在するかどうかを確認し、ブルーム フィルターがまだディスクに書き込まれていないことを示している場合は、それを書き込みます。ブルーム フィルターには偽陰性がありません。
ただし、ブルーム フィルターがディスク上にあると表示している場合は、間違っている可能性があります。

ブルームフィルターが「順列は既に存在する」と言った場合、この候補を終了して、それが本当に既にセットにあるかどうかを確認せずに次の候補に進むかどうかを決定できます。または、ディスクを検索して、それが存在するかどうかを確認できます。本当にそこに。
後者を選択した場合は、ハッシュ テーブルやB+ ツリーなどの順列のスマート DS を維持することを検討する必要があります。

ブルーム フィルターは、ここで完全に一致します。これらは、ここで最も重要なことである偽陰性を 0 にしながら、読み取り範囲が広いセットを表すように設計されています。

于 2012-10-14T17:41:41.370 に答える
4

少し遅れましたが、まだ示されていない方法があると思います。

すべての K 個のアイテムの開始順序と整数インデックスが与えられると、K にほぼ比例する時間で K 個のアイテムのインデックス番目の順列を生成するアルゴリズムがあることを思い出しました。それらの K! ゼロから K までの整数をランダムに生成できる限り、K 個の項目の (階乗) 順列! このルーチンを使用して、メモリ内に N 個の一意のランダム インデックスを生成し、対応する順列をディスクに出力できます。

これは、N を 10 に設定し、k を 25 に設定したアルゴリズムの Python バージョンですが、私は k = 144 を正常に使用しました。

from math import factorial
from copy import copy
import random

def perm_at_index(items, index):
    '''
    >>> for i in range(10):
            print i, perm_at_index([1,2,3], i)

            
    0 [1, 2, 3]
    1 [1, 3, 2]
    2 [2, 1, 3]
    3 [2, 3, 1]
    4 [3, 1, 2]
    5 [3, 2, 1]
    6 [1, 2, 3]
    7 [1, 3, 2]
    8 [2, 1, 3]
    9 [2, 3, 1]
    '''
    
    itms, perm = items[:], []
    itmspop, lenitms, permappend = itms.pop, len(itms), perm.append
    thisfact = factorial(lenitms)
    thisindex = index % thisfact
    while itms:
        thisfact /= lenitms
        thischoice, thisindex = divmod(thisindex, thisfact)
        permappend(itmspop(thischoice))
        lenitms -= 1
    return perm

if __name__ == '__main__':
    N = 10      # Change to 1 million
    k = 25      # Change to 144
    K = ['K%03i' % j for j in range(k)] # ['K000', 'K001', 'K002', 'K003', ...]
    maxperm = factorial(k)              # You need arbitrary length integers for this!
    indices = set(random.randint(0, maxperm) for r in range(N))
    while len(indices) < N:
        indices |= set(random.randint(0, maxperm) for r in range(N - len(indices)))
    for index in indices:
        print (' '.join(perm_at_index(K, index)))

その出力は次のようになります。

K008 K016 K024 K014 K003 K007 K015 K018 K009 K006 K021 K012 K017 K013 K022 K020 K005 K000 K010 K001 K011 K002 K019 K004 K023
K006 K001 K023 K008 K004 K017 K015 K009 K021 K020 K013 K000 K012 K014 K016 K002 K022 K007 K005 K018 K010 K019 K011 K003 K024
K004 K017 K008 K002 K009 K020 K001 K019 K018 K013 K000 K005 K023 K014 K021 K015 K010 K012 K016 K003 K024 K022 K011 K006 K007
K023 K013 K016 K022 K014 K024 K011 K019 K001 K004 K010 K017 K018 K002 K000 K008 K006 K009 K003 K021 K005 K020 K012 K015 K007
K007 K001 K013 K003 K023 K022 K016 K017 K014 K018 K020 K015 K006 K004 K011 K009 K000 K012 K002 K024 K008 K021 K005 K010 K019
K002 K023 K004 K005 K024 K001 K006 K007 K014 K021 K015 K012 K022 K013 K020 K011 K008 K003 K017 K016 K019 K010 K009 K000 K018
K001 K004 K007 K024 K011 K022 K017 K023 K002 K003 K006 K021 K010 K014 K013 K020 K012 K016 K019 K000 K015 K008 K018 K009 K005
K009 K003 K010 K008 K020 K024 K007 K018 K023 K013 K001 K019 K006 K002 K016 K000 K004 K017 K014 K011 K022 K021 K012 K005 K015
K006 K009 K018 K010 K015 K016 K011 K008 K001 K013 K003 K004 K002 K005 K022 K020 K021 K017 K000 K019 K024 K012 K023 K014 K007
K017 K006 K010 K015 K018 K004 K000 K022 K024 K020 K014 K001 K023 K016 K005 K011 K002 K007 K009 K013 K019 K012 K021 K003 K008
于 2012-10-24T20:01:40.413 に答える
0

つまり10! ~= 3e6、K > ~15適切なFischer-YatesまたはKnuthシャッフルを使用してK個のアイテムのリストを100万回シャッフルすると、毎回一意のシャッフルが得られる可能性が非常に高くなります。

100 万個の一意の順列をすべてメモリ内のセット データ構造に保存できる場合は、K 個のアイテムのリストをシャッフルして、100 万個になるまでセットに追加できます。

これは、シャッフルがさまざまな K に対して一意のパーマを生成するのにどれだけ優れているかを示す Python の例です。

>>> from math import factorial
>>> from random import shuffle
>>> 
>>> n = 1000000
>>> for k in range(16, 9, -1):
    perms = set()
    perm = list(range(k))
    trials = 0
    while len(perms) < n:
        trials += 1
        for i in range(n - len(perms)):
            shuffle(perm)
            perms.add(tuple(perm))
    print('N=%i, K=%i, trials=%i, K!//N= %i' % (n, k, trials, factorial(k)//n))


N=1000000, K=16, trials=1, K!//N= 20922789
N=1000000, K=15, trials=1, K!//N= 1307674
N=1000000, K=14, trials=2, K!//N= 87178
N=1000000, K=13, trials=2, K!//N= 6227
N=1000000, K=12, trials=3, K!//N= 479
N=1000000, K=11, trials=5, K!//N= 39
N=1000000, K=10, trials=11, K!//N= 3
>>>
于 2014-08-27T21:45:08.853 に答える
0

これがそれを行う1つの方法です。

1) 最初の N 個の順列を生成し、それらをディスクに保存します。

2) 次に、順列に対してランダム化アルゴリズムを実行します。

Divide and Conquer を使用して、ディスクから最初の X 要素のみを選択してランダム化し、次の反復で次の X 要素などを選択して最適化し、結果をマージできます。

ここではおそらくディスクは必要ありません。

于 2012-10-14T17:41:23.523 に答える