무작위 순열 1,000,000 샘플 생성

Question

많은 정수 순열을 가지고 작업하고 있습니다. 각 순열의 요소 수는 K입니다. 요소 크기는 1 바이트입니다. N 개의 고유 한 무작위 순열을 생성해야합니다.
제약 조건 : K < = 144, N < = 1,000,000.

나는 다음과 같은 간단한 알고리즘을 함께했다 :

1. 는 N 임의 순열의 목록을 생성합니다. 모든 순열을 RAM에 저장하십시오.
2. 목록을 정렬하고 모든 중복 항목을 삭제합니다 (있는 경우). 중복 횟수는 상대적으로 적습니다. 어떤 중복이 있다면
3. , N 순열가 될 때까지 목록에 임의의 순열을 추가하고 2

이 할 수있는 더 나은 방법이 있습니까 단계로 돌아갑니다? 특히, 모든 순열을 RAM에 저장하지 않는 방법이 있습니까 (생성 중에 디스크에 쓰기)?

편집 : 최종적으로 생성 된 순열은 순차적으로 액세스해야합니다 (임의 액세스가 필요 없음). RAM은 더 중요한 요소입니다 (나는 모든 순열을 RAM에 한번에 저장하지 않는 편이 낫습니다).

Answer 1

가능한 해결책은 bloom filters입니다.

디스크에 순열을 저장하고 (순차적으로 씁니다) RAM에 블룸 필터를 유지하십시오.
순열을 생성하면 - 블룸 필터에 존재하는지 확인합니다. 블룸 필터가 디스크에 아직 기록되지 않았다고 쓰면 - 블룸 필터에 거짓 음이 없습니다.
그러나 블룸 필터가 디스크에 있다고 말하면 - 잘못되었을 수 있습니다.

블룸 필터가 "순열이 이미 있음"이라고 말하면이 후보를 종료 할 것인지 결정할 수 있습니다. 다음 세트는 세트에 실제로 있는지 확인하지 않고 디스크를 검색하여 실제로 있는지 확인합니다.
나중에 선택하는 경우 hash table 또는 B+ tree과 같은 순열에 대한 스마트 DS 유지 관리를 고려해야합니다.

Bloom 필터는 여기에 완벽하게 일치합니다.이 필터는 여기에서 가장 중요한 것 인 0 개의 잘못된 음수를 제공하면서 읽기에는 확장 된 세트를 나타내도록 설계되었습니다.

Answer 2

한 가지 방법이 있습니다.

1) 첫 번째 N 순열을 생성하여 디스크에 저장합니다.

2) 그런 다음 순열에 대해 임의 화 알고리즘을 실행하십시오.

Divide and Conquer를 사용하여 디스크의 첫 번째 X 요소 만 선택한 다음 임의로 추출하고 다음 반복에서 다음 X 요소를 선택하여 최적화 할 수 있습니다. 그런 다음 결과를 병합합니다.

아마 여기에 디스크가 필요하지 않습니다.

Answer 3

조금 늦었지만 표시되지 않은 방법이 있다고 생각합니다.

나는 모든 K 항목과 정수 인덱스의 시작 순서가 주어지면 대략 K에 비례하여 K 항목의 인덱스 순열을 생성하는 알고리즘임을 기억했다. K! 0과 K 사이의 정수를 무작위로 생성 할 수있는 한 K 항목의 (팩토리얼) 순열! 루틴을 사용하여 N 개의 고유 한 임의의 인덱스를 메모리에 생성 한 다음 해당 순열을 디스크에 인쇄 할 수 있습니다.

:

가

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))) 

출력이있는 다음과 같은 : I는 K가 = 144이 성공적으로 사용하고 있지만 여기

이 25 N을 10로 설정 K와 알고리즘 파이썬 버전

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 

Answer 4

10! ~= 3e6, 즉 K > ~15이 주어지면 적절한 피셔 - 예이츠 또는 크 누스 셔플을 사용하여 K 항목의 목록을 100 만 번 섞으면 매번 고유 한 셔플을 얻게 될 가능성이 큽니다.

100 만개의 순열을 모두 메모리에 저장할 수 있다면 수백만 개가 될 때까지 K 항목의 목록을 섞어서 세트에 추가 할 수 있습니다.

여기 또한 다양한 고유 파마를 생성에서 셔플이 얼마나 좋은 측정 한 것 몇 가지 파이썬의 K의 :

>>> 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 
>>>