순열 알고리즘 (Permutation Algorithm)

사전순으로 출력되지 않는다는 점을 주의해야겠다.

 

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

 

위와 같이 출력된다. 사전순으로 출력된다면

• 1 2 3
• 1 3 2
• 2 1 3
• 2 3 1
• 3 1 2
• 3 2 1

이어야 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;



/* 순열 알고리즘 */
void Permutation(vector<int>& Array, int Start, int End)
{
    if (Start == End)
    {
        for (const auto it : Array)
        {
            cout << it << " ";
        }
        cout << endl;


    }
    else
    {
        for (int i = Start; i <= End; ++i)
        {
            swap(Array[Start], Array[i]);
            Permutation(Array, Start + 1, End);
            swap(Array[Start], Array[i]);
        }
    }
}

 

 

해당 알고리즘의 수행은 다음과 같습니다:

1. 인자로 배열과, 순열 알고리즘의 시작 인덱스, 순열 알고리즘의 끝 인덱스를 받습니다.
2. 시작 인덱스와 끝 인덱스가 같다면, 원소가 하나이거나 모든 인덱스를 순회했다는 의미이므로 출력합니다.
3. 인덱스가 서로 다르면, 시작부터 끝까지 모든 인덱스에 대해 시작 인덱스와 자리를 바꾸고 시작 인덱스를 1만큼 이동하여 재귀 함수를 호출한 후, 다시 자리를 바꾼 인덱스와 시작 인덱스의 자리를 스왑합니다. (결과적으로, dfs의 느낌을 보입니다.)

 

순열 알고리즘의 동작 순서(출처 : https://jksk0115.tistory.com/112)

위의 재귀를 이용한 알고리즘은 그림에서 알 수 있듯이, 6가지 경우의 수를 도출하기 위해 9 * 2번의 스왑(swap)을 수행하고 있습니다.

 

 

순열 알고리즘 (Permutation Algorithm)