C++로 구현하는 Alexander Bogomolny의 비정렬 순열 알고리즘 – 1부터 N까지의 모든 순열 생성

이 글에서는 Alexander Bogomolny의 비정렬 순열(UnOrdered Permutation) 알고리즘을 C++로 구현하여, 1부터 N까지의 자연수로 만들 수 있는 모든 순열을 생성하고 출력하는 방법을 소개합니다.

알고리즘 개요

이 알고리즘은 재귀 호출과 백트래킹(backtracking)을 기반으로 동작합니다. 각 단계(레벨)마다 아직 사용되지 않은 숫자를 하나씩 배치하고, 모든 숫자가 배치되면 완성된 순열을 출력한 뒤 이전 상태로 되돌아가 나머지 경우를 계속 탐색합니다. 의사 코드로 표현하면 다음과 같습니다.

시작
    함수 AlexanderBogomolny()를 정의하여 알고리즘을 구현한다
    매개변수:
        Val[] = 순열을 저장할 배열
        N     = 입력받은 원소의 개수
        k     = 현재 레벨(단계)
    함수 본문:
        정적(static) 변수 l을 -1로 초기화
        l = l + 1
        Val[k] = l
        if (l == N)
            display(Val, N) 호출하여 완성된 순열 출력
        else
            i = 0 부터 N-1 까지 반복
                if (Val[i] == 0)
                    AlexanderBogomolny(Val, N, i) 재귀 호출
            l = l - 1
            Val[k] = 0
종료

C++ 구현 예제

다음은 위 알고리즘을 그대로 옮긴 전체 소스 코드입니다.

#include<iostream>
#include<iomanip>
using namespace std;

// 완성된 순열을 화면에 출력하는 함수
void display(const int *n, const int size)
{
    int i;
    if (n != 0) {
        for (i = 0; i < size; i++) {
            cout << setw(4) << n[i];
        }
        cout << "\n";
    }
}

void AlexanderBogomolny(int *Val, int N, int k)
{
    static int l = -1;
    int i;
    // 시작 시 레벨을 0으로 설정
    l = l + 1;
    Val[k] = l;
    if (l == N)
        display(Val, N);
    else
        for (i = 0; i < N; i++)
            // 배열 값이 0이면(아직 사용되지 않은 자리라면) 값을 배정
            if (Val[i] == 0)
                AlexanderBogomolny(Val, N, i);
    // 해당 레벨 이후의 모든 순열을 처리한 뒤 레벨을 감소(백트래킹)
    l = l - 1;
    Val[k] = 0;
}

int main()
{
    int i, N, cnt = 1;
    cout << "순열을 만들 자연수의 개수 N을 입력하세요: ";
    cin >> N;
    int Val[N];
    for (i = 0; i < N; i++) {
        Val[i] = 0;
        cnt *= (i + 1);   // N! 계산
    }
    cout << "\n가능한 순열의 개수는: " << cnt;
    cout << "\n\nAlexander Bogomolny 알고리즘을 이용한 순열 \n";
    AlexanderBogomolny(Val, N, 0);
    return 0;
}

코드 핵심 포인트

• static 변수 l: 재귀 호출 전체에서 하나의 값만 유지되며, 현재 채워진 자릿수(레벨)를 나타냅니다.
• 배열 초기화: Val[]의 모든 값을 0으로 초기화하여 '아직 사용되지 않은 자리'를 표시합니다.
• 백트래킹: 한 레벨에서 가능한 모든 분기를 탐색한 후에는 l을 감소시키고 Val[k] = 0으로 되돌려 다른 경우를 시도합니다.

참고: int Val[N]처럼 실행 시점에 크기를 정하는 가변 길이 배열(VLA)은 표준 C++ 사양이 아니며, GCC 등 일부 컴파일러에서만 지원하는 확장 기능입니다. 표준을 준수하려면 std::vector<int> Val(N)을 사용하는 것이 좋습니다.

실행 결과

N = 5를 입력하면 먼저 가능한 순열의 개수인 5! = 120이 출력되고, 이어서 120개의 순열이 모두 출력됩니다. 아래는 출력 결과의 앞부분입니다.

순열을 만들 자연수의 개수 N을 입력하세요: 5
가능한 순열의 개수는: 120

Alexander Bogomolny 알고리즘을 이용한 순열
   1   2   3   4   5
   1   2   3   5   4
   1   2   4   3   5
   1   2   5   3   4
   1   2   4   5   3
   1   2   5   4   3
   1   3   2   4   5
   1   3   2   5   4
   ...
   5   4   2   3   1
   5   4   3   2   1

이처럼 첫 번째 숫자가 1인 순열부터 5로 시작하는 순열까지, 총 120개(N!)의 모든 순열이 체계적으로 출력됩니다. 시간 복잡도는 순열의 개수에 비례하므로 O(N × N!)이며, N이 커질수록 결과의 수가 급격히 늘어난다는 점을 유의해야 합니다.