완전순열(교란순열)

알고리즘/자료구조 2016.12.04 20:52 Posted by 아는 개발자

어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다.


 X2

X1 

X4 

X3 


점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다.


공식은 다음과 같다


a(n) = (n-1) * (a(n-1) + a(n-2))


증명을 하면,


1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다.


- X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.

- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다.


1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 위와 동일하게


a(N) = (N-1) * (a(N-1) + a(N-2)) 가 나온다.


위의 경우처럼 단순히 원소들이 자기의 위치에 존재하지 않는 경우만 생각하면 별 쓰임이 없을 것 같은데,

여러 원소들을 분산해서 써야하는 경우를 생각하면 쓸데가 있다.

(결론은 기억은 해두자)

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05