임의의 순서로 이루어진 순열 얻기

배열을 임의의 순서로 뒤바꾸기 위해서는 여러 알고리즘을 사용한다.

1. PERMUTE_BY_SORTING

PERMUTE_BY_SORTING

1    n <- length[A]

2    for i <- 1 to n

3        do P[i] = RANDOM(1,n^3)

4    return A

array[A] = <1,2,3,4>

array[P] = <36,3,97,19>

result : array[A] = <2,4,1,3>

> n^3를 얻는 이유는 P의 모든 우선순위들이 서로 다른 값을 가지기 위해서이다( 1- 1/n)

동일한 순열을 얻게 되는 확률은 1/n!

Time : 오메가( n lg n)

2. RANDOMIZE-IN-PLACE

RANDOMIZE-IN-PLACE

1    n <- length[A]

2    for i <- 1 to n

3        do A[i] <-> A[ RANDOM( i , n ) ]

순열은 모두 n!/(n-k)!개가 존재한다.

확률은 1/n!

Time : 오메가( n )

> 균등순열을 얻는 확률로 A[i]가 j번째에 존재하는 확률이 1/n으로는 부족하다.

> 개인적으로 쓰는 알고리즘은 2. RANDOMIZE-IN-PLACE이다.