알고리즘/ Permutation cycle

Permutation cycle에 대한 설명은 위에 다있으니

생략 하도록 하고

프로그래밍 하는 방법만 설명 드리겠습니다.

먼저 숫자가 위와 같이

4  1  7  5  6  8  3  9  10  2 이라고 치면

이만큼 길이의 boolean 배열을 선언합니다.(c언어라면 그냥 int로 하면되겠죠)

그리고 permutation cycle의 갯수를 세주는 count변수를 하나 둡니다.

Number	1	2	3	4	5	6	7	8	9	10
boolean	false	false	false	false	false	false	false	false	false	false

처음은 이렇게 모두 false로 둡니다. 그리고 1부터 따라갑니다.

Number	1	2	3	4	5	6	7	8	9	10
boolean	true	false	false	false	false	false	false	false	false	false

 1->4 이죠? 지나간길을 true로 바꿉니다.

 

Number	1	2	3	4	5	6	7	8	9	10
boolean	true	false	false	true	true	true	false	true	true	true

1->4->5->6->8->9->10->2

 여기까지 갔을때 2다음에 1로 가야합니다 2->1 

근데 1이 이미 true가 되있기 때문에  2는 true로 만들어 주고 count변수를 증가시켜줍니다

count==1

Number	1	2	3	4	5	6	7	8	9	10
boolean	true	true	false	true	true	true	false	true	true	true

그리고 오름차순으로 false인 수를 찾습니다.

false인것 중에 가장 작은수가 3이겠죠?

그럼 3에서 부터 다시 따라갑니다.

3->7까지 하고 7에서 3으로 갈때 3이 true이므로 count변수를 다시 증가시켜주고 지나온 7은 true로 만들어 줍니다.

count==2

 

Number	1	2	3	4	5	6	7	8	9	10
boolean	true	true	true	true	true	true	true	true	true	true

모두 true가 되었기때문에 

프로그램이 끝났습니다.

count변수는현재 2겠죠 .

그래서 permutation cycle의 갯수는 2입니다.

이런식으로 boolean 배열을 이용해서 풀면 되겠습니다.

더 좋은 방법이 있을지 모르겠지만  ㅋ 

 다른방법은 잘 모르겠습니다. ㅋ