지정한 개수의 모든 순열을 출력하는 C++ 언어 소스

정의  (순열(또는 치환), permutation)

S가 집합일 때, S에서 S 위로 가는 일대일함수 즉, S에서 S로 가는 전단사함수를 집합 S 위에서의 순열이라고 한다, 특히 S가 원소 n개를 갖는 유한집합인 경우 S 위에서의 서로 다른 순열은 총 n!(n 팩토리얼)개이다.

 

다음의 C++ 언어로 작성된 소스는 유한집합 S = { 0, 1, 2, ... , n - 1 } 상에서의 모든 순열을 컨솔에 출력해준다. 우순열(even permutation)인지 기순열(odd permutation)인지도 판별해준다.

컴파일은 g++ 또는 Visual C++ 의 명령줄 컴파일러 cl 을 이용한다.

 

// Filename: permutations.cpp
//
// Compile: g++ -std=c++11 -o permutations permutations.cpp
// Execute: ./permutations [integer]
//
//     or
//
// Compile: cl /EHsc permutations.cpp
// Execute: permutations [integer]
//
// Date: 2013. 9. 20.

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

using namespace std;

void printVector(const vector<int> v, int counter)
{
    int n = v.size();
    cout << "[";
    if (n > 0)
    {
        cout << " " << v[0];
        if (n > 1)
        {
            for (int i = 1; i < n; i++)
            {
                cout << ", " << v[i];
            }
        }
        cout << " ";
    }
    cout << "]";
    if ((counter % 2) == 0)
        cout << "    -- even --";
    else
        cout << "    -- odd  --";
    cout << endl;
}

void swap(vector<int> &v, int i, int j)
{
    int x = v[j];
    v[j] = v[i];
    v[i] = x;
}

void doPermute(vector<int> v, int size, int &cnt)
{
    if (size == 2)
    {
        printVector(v, cnt);
        swap(v, 0, 1);
        cnt++;
        printVector(v, cnt);
        swap(v, 0, 1);
        cnt--;
    }
    else if (size > 2)
    {
        doPermute(v, size - 1, cnt);
        for (int i = size - 2; i >= 0; i--)
        {
            swap(v, i, size - 1);
            cnt++;
            doPermute(v, size - 1, cnt);
        }
        for (int i = 0; i <= size - 2; i++)
        {
            swap(v, i, size - 1);
            cnt--;
        }
    }
}

int main(int argc, const char *argv[])
{
    // vector<int> v = { 0, 1, 2, 3, 4 };     // syntax  for c++11
    vector<int> v(5);
    for (int i = 0; i < 5; i++)
    {
        v[i] = i;
    }

    int counter = 0;
    int k = 3;

    if (argc > 1)
    {
        sscanf(argv[1], "%d", &k);
    }

    if (k > 5)
    {
        for (int i = 6; i <= k; i++)
        {
            v.push_back(i);
        }
    }
    else if (k < 5) {
       for (int i = 0; i < 5 - k; i++)
       {
          v.pop_back();
       }
    }

    doPermute(v, k, counter);

    return 0;
}

/*
Execute & Output:

$ ./permutations
[ 0, 1, 2 ]    -- even --
[ 1, 0, 2 ]    -- odd  --
[ 0, 2, 1 ]    -- odd  --
[ 2, 0, 1 ]    -- even --
[ 1, 2, 0 ]    -- even --
[ 2, 1, 0 ]    -- odd  --

$ ./permutations 2
[ 0, 1 ]    -- even --
[ 1, 0 ]    -- odd  --

$ ./permutations 4
[ 0, 1, 2, 3 ]    -- even --
[ 1, 0, 2, 3 ]    -- odd  --
[ 0, 2, 1, 3 ]    -- odd  --
[ 2, 0, 1, 3 ]    -- even --
[ 1, 2, 0, 3 ]    -- even --
[ 2, 1, 0, 3 ]    -- odd  --
[ 0, 1, 3, 2 ]    -- odd  --
[ 1, 0, 3, 2 ]    -- even --
[ 0, 3, 1, 2 ]    -- even --
[ 3, 0, 1, 2 ]    -- odd  --
[ 1, 3, 0, 2 ]    -- odd  --
[ 3, 1, 0, 2 ]    -- even --
[ 0, 2, 3, 1 ]    -- even --
[ 2, 0, 3, 1 ]    -- odd  --
[ 0, 3, 2, 1 ]    -- odd  --
[ 3, 0, 2, 1 ]    -- even --
[ 2, 3, 0, 1 ]    -- even --
[ 3, 2, 0, 1 ]    -- odd  --
[ 1, 2, 3, 0 ]    -- odd  --
[ 2, 1, 3, 0 ]    -- even --
[ 1, 3, 2, 0 ]    -- even --
[ 3, 1, 2, 0 ]    -- odd  --
[ 2, 3, 1, 0 ]    -- odd  --
[ 3, 2, 1, 0 ]    -- even --
*/