O (N)에서 대체가없는 k 개의 무작위 순열 대체

Question

교체없이 목록의 고유 한 임의 순열이 효율적으로 필요합니다. 나의 현재의 접근 방식 :

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] 

get_nth_permutation이 효율적으로, 같은 소리 정확히 않는 곳 (O 의미 (N)). 그러나 이것은 len(population) <= 20에 대해서만 작동합니다. 21 일뿐입니다! 그래서 mindblowingly 긴 xrange(math.factorial(21))이 작동하지 않을 것입니다 :

OverflowError: Python int too large to convert to C long 

인가가 O (N)에 교체하지 않고 고유의 순열 케이 샘플 더 나은 알고리즘은?

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은 일반적인 방식으로 내 요점을 반복합니다. 또한 위키 피 디아가이 문제에 관해 무엇을 말하고 있는지 확인하십시오. here.