Number of Swap Operations

오늘 우연찮게 찾아본 자료.. 이참에 정리해두는게 낫겠다..


어떤 1~n 까지의 수의 permutation을 정렬하기 위해 최소 몇번의 swap operation이 필요할까?

1. 이웃하는 수끼리만 swap이 가능하다면 bubble sort시 swap 이 일어나는 개수와 같다..
2. 임의의 수끼리 swap이 가능하다면 아래의 방법을 사용한다..

Let's take for example your data 4 2 3 1. It can be rewriten this way (14)(2)(3). Here we see one cycle of length 2 and two of length 1. The key idea is that: to sort a cycle optimally we need (length-1) operations. So here we need (2-1)+(1-1)+(1-1) swaps.
 
Another example 2 3 1. Its cycle representation is (123) - one cycle of length 3 - so we need 2 swaps to sort it.

UVa 보드에서 퍼온 글인데.. 이와 관련되어 유용한 내용이 많다..


관련문제:
299 - Train Swapping
10570 - Meeting with Aliens


ps)
오늘 아침 10시에 탑코더가 열렸었는데.. 후배 한명이 Div2 500점 문제를 풀다가 # of swap operation에 대해서 마구 물어보길래.. 잽싸게 자료를 찾아서 설명해줬다.. 나중에 문제를 읽어봤는데.. # of swap operation과는 전혀 상관없는 문제잖아.. -_-