[algorithm] O (1)의 고유 한 (반복되지 않는) 난수?

값을 0-1000으로 1001 개의 정수 배열을 초기화하고 변수 max를 배열의 현재 최대 인덱스 (1000으로 시작)로 설정하십시오. 0에서 최대 사이의 난수 r을 선택하고, 위치 r에있는 숫자를 최대 위치에있는 숫자로 바꾸고, 이제 최대 위치에있는 숫자를 반환하십시오. 최대 값을 1 씩 줄이고 계속하십시오. max가 0 인 경우 max를 배열의 크기-1로 다시 설정하고 배열을 다시 초기화 할 필요없이 다시 시작하십시오.

업데이트 :
질문에 대답했을 때이 방법을 스스로 생각해 냈지만 일부 연구 후에 이것이 Durstenfeld-Fisher-Yates 또는 Knuth-Fisher-Yates로 알려진 수정 된 버전의 Fisher-Yates 임을 알았습니다. 설명하기가 약간 어려울 수 있으므로 아래 예제를 제공했습니다 (1001 대신 11 요소 사용).

11 개의 요소가 array [n] = n으로 초기화 된 상태에서 배열이 시작되고 최대 값은 10에서 시작합니다.

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
                                ^
                               max

각 반복에서 임의의 숫자 r이 0과 최대 사이에서 선택되고 array [r]과 array [max]가 바뀌고 새 배열 [max]가 반환되고 max가 감소합니다.

max = 10, r = 3
           +--------------------+
           v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                       +-----+
                       v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
     +--------------------+
     v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
                 +-----+
                 v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

11 회 반복 한 후 배열의 모든 숫자가 선택되고 max == 0이되고 배열 요소가 섞입니다.

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

이 시점에서 최대 값을 10으로 재설정하고 프로세스를 계속할 수 있습니다.

답변

000   733
001   374
002   882
003   684
004   593
005   578
006   233
007   811
008   072
009   337
010   119
011   103
012   797
013   257
014   932
015   433
...   ...

unsigned randperm(string key, unsigned bits, unsigned index) {
  unsigned half1 =  bits    / 2;
  unsigned half2 = (bits+1) / 2;
  unsigned mask1 = (1 << half1) - 1;
  unsigned mask2 = (1 << half2) - 1;
  for (int round=0; round<5; ++round) {
    unsigned temp = (index >> half1);
    temp = (temp << 4) + round;
    index ^= hash( key + "/" + int2str(temp) ) & mask1;
    index = ((index & mask2) << half1) | ((index >> half2) & mask1);
  }
  return index;
}