무작위 순열

랜덤 순열은 객체 집합, 즉 순열 값 랜덤 변수의 랜덤 순서다.무작위 순열의 사용은 종종 코딩 이론, 암호학, 시뮬레이션과 같은 무작위화된 알고리즘을 사용하는 분야에서 기본이 되는 경우가 많다.무작위 순열의 좋은 예는 카드 한 벌의 섞임이다: 이상적으로는 52개의 카드를 무작위로 순열하는 것이다.

임의 순열 생성

진입별 가압력법

길이 n 집합의 임의 순열을 무작위로 균일하게 생성하는 한 가지 방법(즉, 각 n! 순열은 동일하게 나타날 가능성이 있음)은 1과 n 사이의 난수를 순차적으로 취하여 반복이 없음을 확인하고, 이 순서(x₁_n, ..., x)를 순열로 해석하는 것이다.

{\pmatrix}1&gt;2&3&\cdots &n\\n3&\cdots &x_{1}x_{1}{1}x_{2}&x_{3}&\cdots &x_{n}\end{pmatrix}},},},},

여기에 2행 표기법으로 표시한다.

이 무차별적인 방법은 무작위로 선택한 숫자가 이미 선택한 숫자의 반복일 때마다 가끔 재시도를 해야 한다.ih 단계(x₁, ..., x가_{i − 1} 이미 선택되었을 때)에서 1과 n - i + 1 사이의 임의로 숫자 j를 선택하고 x를_i 언초센 수 중 j번째로 큰 숫자와 같게 설정하는 경우 이를 피할 수 있다.

피셔-예이츠 슈플스

피셔-예이츠 셔플(Fisher-Yates shuffle)이라고 하는 재시도 없이 무작위로 n개 항목의 순열을 생성하는 간단한 알고리즘은 모든 순열(예: ID 순열)에서 시작하여 0~n - 2(첫 번째 원소가 지수 0을 가지고 있고 마지막 원소가 지수 n - 1을 갖는 규약을 사용한다), and 각 위치에 대해 i에서 n - 1(끝)까지 임의로 선택한 요소와 현재 있는 요소를 교환한다.정확히 1/n!의 확률로 이 알고리즘에 의해 n 요소의 순열이 생성됨을 쉽게 검증할 수 있으므로 이러한 순열에 대해 균일한 분포를 산출할 수 있다.

서명이 없는 획일적인(서명이 없는 m); /* 랜덤 정수 0 <= 균일(m) > = m-1을 균일한 분포로 반환 */  공허하게 하다 initialize_and_initialize(서명이 없는 순열[], 서명이 없는 n) {     서명이 없는 i;     을 위해 (i = 0; i <= n-2; i++) {         서명이 없는 j = i+획일적인(n-i); /* i ≤ j < n */와 같은 임의의 정수         바꾸다(순열[i], 순열[j]);   /* 임의로 선택한 요소를 순열[i] */로 교체하십시오.     } }

다음 경우에 주의하십시오.uniform()기능은 단순히 다음과 같이 구현된다.random() % (m)다음, 결과의 편향은 다음 값들의 반환 값들의 수가random()m의 배수는 아니지만, 만약 반환값의 수가random()m보다 큰 규모의 주문이다.