선형 시간 상수 공간 순열 생성기

Question

j 번째 순열의 i 번째 요소 (0 < = i < n)를 결정적으로 일정한 시간과 공간에서 반환하는 생성 함수 f (i, j, n) 0 < = j < n!)의 첫 번째 n 정수 중? 그렇다면 어떻게 작동합니까? 그렇지 않다면 반발을 볼 수 있습니까?

이 질문은이 일에 관련이있다 : Create a random permutation of 1..N in constant space 그러나,이 경우, 우리는 일본의 우리의 선택이 아니라 특정 또는 임의의 하나에 따라 마다 순열을 생성 할 수 있어야합니다.

Random access random permutations (사실,이 질문의 작성자가 갖고 싶어했을만한 것일 수도 있습니다. 더 구체적이고 제한적이지는 않습니다. 어떤 경우에는 병렬화에 관심이 없습니다.)

그렇다면 매개 변수 j (길이가 O (n)이므로)를 제거하고 순열을 생성 할 수 있는지 알고 싶습니다. 먼저 이름을 지정하지 않고 무작위로 일정하게 선택합니다.

만약 가능하지 않다면, 확률 적으로 (하지만 여전히 결정론적인 선형 시간과 일정 공간에서) 균일하게 선택된 순열을 생성 할 수 있는지 궁금합니다. 예를 들어, 일률적으로 선택된 시퀀스를 생성하는 방법으로, 순열이 1 %보다 큰 경우도 있습니다.

내가 순열을 생성하기 위해 알고있는 모든 방법은 값의 범위를 명시 적으로 저장하거나 적어도 지금까지 생성 된 모든 숫자를 저장해야하기 때문에이 질문을하고 있습니다.

Answer 1

나는 얼마 전에 this problem와 비슷한 것을 시도했다.

문제를 약간 수정하면 j 번째 순열을 직접 생성 한 다음 i 번째 요소를 선택합니다.

#!/usr/bin/env python3 

from math import factorial 

def getJthPermutation(initList, j): 
    j -= 1 

    result = "" 
    fac = factorial(len(initList) - 1) 
    for div in range(len(initList) - 1, 0, -1): 
     k = j // fac 
     result += initList[k] 
     del initList[k] 

     j %= fac 

     fac //= div 
    result += initList[0] 

    return result 


def fct(i, j, n): 
    list = [str(k) for k in range(n+1)] 

    permutation = getNPermutation(list[:], j) 

    return permutation[i] 


if __name__ == "__main__": 
    print(fct(3,1000000,9)) 
    print(fct(3,1,9)) 
    print(fct(1,factorial(9), 9)) 

(if you don't have python installed)

여전히하지만 i도 j에 n에 따라 달라 것이다 복잡성 (I 착각하지 않다 경우).