ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 완전순열(교란순열)
    알고리즘/자료구조 2016. 12. 4. 20:52

    어떤 배열의 원소 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

    댓글 0

Designed by Tistory.