62. 순열(Permutation) 출력 및 사전순서 출력 알고리즘

1. 개요

순열(Permutation)은 n개의 원소 중 k개를 뽑아서, 나열하는 것이다.

조합(Combination)이 단순히 n개의 원소 중 k개를 뽑아내는 경우만을 찾아서 부분집합을 만들 수 있었다면,

순열은 이런 부분집합들의 나열하는 방법을 일컫는다.

지금까지 set배열과 set_size를 통한 코드 구조가 안먹힌다.

재귀 코드의 형태가 조금 다른데, 문제는 단순 순열 출력이 아닌 이를 사전 순으로 출력하는데 있다.

두 가지 방식, 일반적인 순열 출력 알고리즘과 사전 순으로 순열을 출력하는 알고리즘 두 개가 있으며,

사전 순으로 순열을 출력하는 방식은 처음 보는 방식이었다.

그래서 더욱 놀랍다.

생각의 범위라는게 조금씩 확장되는 듯한 느낌? 아마 이것을 그냥 짜라고 했다면 못짰다. 틀을 알고있으니까 짜는거지.

Right_Rotate() 함수와 Left_Rotate() 함수를 이렇게 이용할 줄은 진짜 꿈에도 몰랐다. 신기하다.

아마 나같았으면 계속 정렬하는 말도 안되는 방식을 짰겠지. 대단하다. 사람의 머리란.

전체적인 알고리즘의 틀은 이렇다.

0 1 2 3의 순열은 총 4가지로 나뉘는데,

0 | 1 2 3 의 순열

1 | 0 2 3 의 순열

2 | 0 1 3 의 순열

3 | 0 1 2 의 순열

이렇게 나뉘고, 또 길이 3에서

---------------------------------

0 | 1 2 3

1 | 2 3

2 | 1 3

3 | 1 2

---------------------------------

1 | 0 2 3

0 | 2 3

2 | 0 3

3 | 0 2

---------------------------------

2 | 0 1 3

0 | 1 3

1 | 0 3

3 | 0 1

---------------------------------

3 | 0 1 2

0 | 1 2

1 | 0 2

2 | 0 1

---------------------------------

이렇게 계속 재귀적으로 풀어나간다.

이것이 순열의 기본 알고리즘이다. (나중에 아무런 참고자료없이 꼭 다시 반복해서 짜보자.)

2. 문제

순열(Permutation) 출력 알고리즘을 작성하시오. (사전 순으로도 출력하는 알고리즘도 작성하시오.)

3. 코드 및 출력

3-1) Perm()

3-2) Perm_Dictionary()

3-3) 출력

마지막 출력은 맨 처음 출력을 사전 순으로 출력할 때, 쉽게 이해되게 하기위해서 Rotate()연산 후의 변환 과정을 보인다.

4. 정리

이렇게 순열 알고리즘도 끝났다. 오늘 남은 건 이제 괄호쌍 알고리즘이다.