랜덤 순열 = 난

Question

보통 N 요소 어레이에 대한 임의의 순열 n! 가능성에서 균일 한 분포를 의미하며, 누스 셔플 그렇게 사용된다

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i 
    exchange a[j] and a[i] 

그러나로를 제약이 a[i] != i인데, 나는 그러한 순열을 어떻게 균일하게 형성해야하는지 모른다.

예를 들어, n = 3 인 경우, 아래의 가능성으로부터 무작위로 순열을 형성하는 방법은 무엇입니까? 고정 점없이

{1, 2, 0}, {2, 0, 1}

Answer 1

순열 derangemets 수로

derangement가 O 인 호출 (N!)를 그냥 순열들의 수와 같은, 모든 순열을 생성하고 있지 않은 그 필터링 정신 착란은 당신의 성적을 해치지 않을 것입니다.

빠른 검색은 다른 알고리즘을 설명하는 these slides을 반환했습니다.

Answer 2

배열의 크기 또는 효율성에 대해 언급하지 않았습니다. 한 가지 가능한 해결책은 크 누스 셔플을하는 것입니다. 그런 다음 구속 조건이 만족되는지 확인하고 그렇지 않은 경우 셔플을 다시 실행하십시오.

효율성을 좀 더 높이려면이 방법을 시도해보십시오. i이 감소하고 있으므로 exchange a[j] and a[i] 단계 이후에 a[i]이 수정됩니다. 그래서 단순히 알고리즘 수정 :

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i; repeat until a[j] != i 
    exchange a[j] and a[i]