마지막 결과와 씨앗을 기준으로 간격에서 임의의 정수를 반환합니다.

Question

정수의 간격이 있다고 가정합니다 [A, B].반복없이 간격 내에서 임의의 구성원을 반환하는 기능을 갖고 싶습니다.간격 내의 모든 구성원이 탐색되면 함수가 동일한 순서로 동일한 첫 번째 임의 순서를 다시 반환하기 시작합니다.

예 : a= 1, b= 5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

.

A와 B 사이의 모든 요소의 배열을 셔플하고 배열이 완료되면 반복되는 것은 쉽습니다.그러나 이것은 너무 많은 메모리 공간을 차지할 것이며, 이것은 내 경우에 적합하지 않습니다 (나는 수백만의 요소를 가질 수 있음)

대신, 내가 가진 기능은 다음과 같이 더 많거나 적습니다.

f(a, b, n, seed) -> n+1

.

여기서,

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

.

트릭은 이전에 반환 된 요소에서만 기반한 간격으로부터 반복되지 않는 숫자를 얻는 방법을 알고 있습니다.결국에는 초기화시 무작위로 원형 목록처럼 작동하지만 메모리 공간을 사용하지 않고

Answer 1

범위 $ [a, b] $ , 즉 생체 내용 함수 . 그런 다음 $ i= a $ 에서 시작하는 카운터 $ i $ 을 유지하십시오. 각 단계에서 $ \ pi (i) $ 을 $ i $ 증분 증분 (주위에 포장 그 $ b + 1 $ 은 $ a $ 이됩니다.

암호화 문헌에서 이러한 임의의 순열을 생성하기위한 표준 방법이 있습니다. 즉, 형식 보존 암호화를 조회하십시오. 시드는 암호화 키입니다. $ o (1) $ 시간과 시간을 계산할 수 있습니다. $ o (1) $ 공간이므로 매우 효율적이어야하며 많은 저장의 필요성을 피해야합니다.

다음 출력이 이전 출력의 함수가되어야한다고 주장하는 경우 $ g (i)= i + 1 $ (< Span 클래스="수학 용기"> $ g (b)= a $ ), $ f (i)= pi ^ {- 1} (g (\ pi (i)) $ , $ \ pi $ 은 위와 같이 선택된 임의의 순열입니다. 그러면 이렇게하면 반복되는 임의의 순환을 제공합니다. $ [a, b] $ 의 요소를 임의의 순서로 $ f (a) , f (f (a)), f (f (f (f (a))), \ dots $ .