알파벳의 n 번째 6 문자 순열 계산

Question

나는이 문제에 대한 해결책을 찾기 위해 수 일간 연구했다. 필요한 경우 컨설팅 시간에 누군가에게 돈을 지불하면 행복 할 것입니다.

저는 현재 파이썬 itertools을 사용하여 32 문자 알파벳의 6 문자 순열을 생성하고 있습니다. 다음 명령을 통해 :

gen = itertools.permutations('ABCDEFGHJKLMNPQRSTUVWXYZ23456789',6) 

설명서에서이 함수는 "r- 길이 튜플, 가능한 모든 순서, 반복되는 요소 없음"을 생성합니다. 내가 얻을

gen2 = itertools.islice(gen,0,10) 

가 결과 2 세대의 반복 :

이 예는 처음 10 순열, 0-10을 잡고 (다음 명령을 통해 결과 순열의 조각을 잡기 위해 라이브러리를 사용할 수 있습니다 정확히 내가 원하는 :

('A', 'B', 'C', 'D', 'E', 'F') 
('A', 'B', 'C', 'D', 'E', 'G') 
('A', 'B', 'C', 'D', 'E', 'H') 
('A', 'B', 'C', 'D', 'E', 'J') 
('A', 'B', 'C', 'D', 'E', 'K') 
('A', 'B', 'C', 'D', 'E', 'L') 
('A', 'B', 'C', 'D', 'E', 'M') 
('A', 'B', 'C', 'D', 'E', 'N') 
('A', 'B', 'C', 'D', 'E', 'P') 
('A', 'B', 'C', 'D', 'E', 'Q') 

이 매우 중요하지만 내 진짜 욕망은 임의의 순열을 선택하고 (모든 가능한 순열 값을 저장하지 않고) 순열 목록에서 잡을 수있을 것입니다 내 계산합니다. 6자를 생성 할 때 정확하다. 위에 나열된 알파벳 순서에는 652,458,240 개의 가능한 조합이 있습니다. 그래서 나는 10,353,345 번째 순열을 부여 잡는 것과 같은 것을 할 수 있기를 바란다. 문제는 위의 islice 함수를 사용하여이 순열을 가져 오는 경우 순열의 전체 집합을 최대 10,353,345 번째 요소로 반복하기 전에 반복해야한다는 것입니다. 상상할 수 있듯이 이것은 매우 비효율적이며 돌아 오는 데 오랜 시간이 걸립니다.

제 질문은 원하는 계산을 수행하는 알고리즘은 무엇입니까? 나는 factorial decomposition과 base n conversion에 관한 많은 연구를 해왔지만, 내가 원하는 것에 가까운 것을 얻기위한 방법이나이 결과를 얻기 위해 수정할 수있는 알고리즘을 찾을 수 없었다.

도움이 될 것입니다.

Answer 1

찾고있는 것은 조합 알고리즘에서 unrank입니다. 고정 된 순서로 집합 S의 요소 목록을 고려해 보면 unrank_S(i)은 목록을 계산하지 않고 목록의 i 번째 요소를 반환합니다. 그래서 여기 S은 Perm(n, k)입니다 : k- 전체 집합의 목록은 n 세트입니다. 이 세트의 크기는 n!/k!입니다.

def factorial(n): 
    if n == 0: return 1 
    return n*factorial(n-1) 

def unrank(S, k, i): 
    S = list(S) # make a copy to avoid destroying the list 
    n = len(S) 
    nb = factorial(n) // factorial(n-k) 
    if i >= nb: 
     raise IndexError 
    res = [] 
    while k > 0: 
     nb = nb // n 
     pos = i // nb # the factoradic digits 
     i = i % nb  # the remaining digits 
     res.append(S[pos]) 
     del S[pos] 
     k = k-1 
     n = n-1 
    return res 

그런

[unrank(range(5), 2, i) for i in range(20)] 
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3]] 

및

unrank(list('ABCDEFGHJKLMNPQRSTUVWXYZ23456789'),6, 128347238)\ 
['G', 'L', 'E', 'H', 'T', 'R'] 

물론 당신이 할 수 있습니다 : 그렇게하는 한 가지 방법은 다음

Factoradic numbers 파이썬의 unrank 알고리즘 사용하는 것입니다 더 나은 방법을 사용하여 계승을 계산하거나 심지어 미리 계산 된 배열로 캐쉬하여 리코를 피하십시오. 그것을 mputing.

Answer 2

완벽한 솔루션을 제공 할 시간이별로 없지만 다음 아이디어는 생각할 줄을 제공 할 수 있습니다.

는 한 번에 6 문자를 복용 N ^일 순열을 찾을 필요가있다.
첫 번째 문자를 수정합니다. 그런 다음 25 개의 다른 문자가 남아 있습니다.
나머지 문자의 총 순열 수는 입니다. P = C * 5!.

따라서 을 첫 번째 문자로 사용하면 P 순열을 가질 수 있습니다. P이 N보다 작 으면 을 처음으로 사용할 수 없습니다.

지금 2 * P이다 첫번째 장소에서 B까지 순열의 처음과 총 숫자에 B을 유지한다.

가 K와 P K ^{일까지 순열의 총 수는} 문자 K *되도록 당신이 처음에 K 문자 번째 유지 말 * P 적은 N보다 및 유지 후 K + 1 문자, (K + 1) * P은 N을 초과한다. 따라서 필요한 문자열은 K + 1 ^번째 문자가 필요합니다.

따라서 N-K * P 나머지 순열을 찾아야합니다. 나머지 25 자와 5 곳이 있습니다. 동일한 문제가 1 문자 줄이며, 1 자리 작고 더 적은 수의 순열을 찾습니다.
그래서 모든 장소에서 비슷한 방식으로 해결하십시오.