순열

요새 바빠가지구 포스팅을 잘 못했네요 호호..

피곤에 쪄들었어요.

그래도 다시 마음잡고 열심히 공부해야죠!

세상 만사가 귀찮아 흑흑

 

사람이 12명씩 서로 2명씩 인사하면 몇 가지의 경우의 수가 나오나요?

바로 66가지의 경우의 수가 나옵니다.

 

경우의 수를 구할 때 보통 순열과 조합을 이용합니다.

 

먼저 순열부터 알아보시죠.

 

순열(Permutation)이란 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산을 말합니다.

예를 들어 1, 2, 3이 있으면 1, 3, 2

2, 1, 3 뭐 이런식으로 말이죠.

그리고 n개의 집합 중에서 n개를 고르는 순열의 개수는 n!(팩토리얼)이라는 특징을 가지고 있습니다.

 

그러면 위에 예시처럼 1, 2, 3을 통해 만들 수 있는 3자리는 과연 몇 개 일까요?

123, 132, 213, 231, 312, 321 이렇게 총 6개를 만들 수 있습니다.

그렇다면 1, 2, 3 중 1자리 자연수는 몇 개 일까요?

3개죠.

3개중에 3개를 뽑는 것이 3! = 6이 되고 3개중에 1개를 뽑는 것은 3이 됩니다.

순열 공식

위 사진처럼 순열 공식이 있는데요.

n은 전체 개수 집합이며 r은 뽑는 개수입니다.

3개 중에 3개를 뽑는다면 3! / (3-3)!이기 때문에 3!

3개 중에 1개를 뽑는다면 3! / (3-1)!이기 때문에 3이 됩니다.

3 * 2 * 1 / 2 * 1 = 3이죠?

 

코드에서는 이것을 간단한게 STL 라이브러리를 통해 사용할 수 있습니다.

next_permutation과 prev_permutation을 이용합니다.

 

오름차순의 배열은 next_permutation을 사용하면 되며,

내림차순의 배열은 prev_permutation을 사용하면 됩니다.

 

next_permutation과 prev_permutation을 사용할 때의 주의사항이 있습니다.

 

방금 말씀 드렸듯이 오름차순은 next_permutation 내림차순은 prev_permutation을 사용한다 했습니다.

#include <iostream>
#include <vector>

using namespace std;

void printV(vector<int> &v)
{
    for (int i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";
    }
    
    cout << '\n';
}

int main()
{
    int arr[3] = { 1, 2, 3 };
    vector<int> vec;
    
    // 오름차순 순열
    for (int i = 0; i < 3; ++i)
    {
        vec.push_back(arr[i]);
    }
    
    do
    {
        printV(v);
    }while(next_permutation(vec.begin(), vec.end()));
}

 

이렇게 오름차순으로 순열을 하는 코드가 있습니다 

보시면 1, 2, 3 순서대로 넣은 게 보이시나요?

네 주의할 사항은 여겁니다.

꼭 오름차순으로 순열을 뽑으시면 순서를 맞추어 주어야 합니다.

 

만약 정렬되지 않은 배열이라면 순열함수가 제대로 작동안할 수 있습니다.

 

예를 들어 3, 2, 1이 들어왔다고 쳐봅시다.

그렇다면 

    int arr[3] = { 3, 2, 1 };
    vector<int> vec;
    
    // 정렬되지 않은 배열
    for (int i = 0; i < 3; ++i)
    {
        vec.push_back(arr[i]);
    }
    
    do
    {
        printV(v);
    }while(next_permutation(vec.begin(), vec.end()));

 

정렬되지 않은 배열이 들어오는데 여기서 next_permutation의 원리를 알아볼 수 있습니다.

지금 들어온 vec.begin() ~ vec.end()사이즈에서 새로운 순열을 만들려고 next_permutation을 실행하는데

3, 2, 1로 다음 순열을 만드는데, 다음 순열이 없습니다.

그야 당연하듯이 123, 132, 213, 231, 312, [321] <-마지막 순열이기 때문이죠.

그렇기에 처음부분인 123을 만들고 false를 반환하기에 한번만 반복하고 끝납니다.

 

내림차순도 똑같습니다.

 

    int arr[3] = { 3, 2, 1 };
    vector<int> vec;
    
    // 내림차순 배열
    for (int i = 0; i < 3; ++i)
    {
        vec.push_back(arr[i]);
    }
    
    do
    {
        printV(v);
    }while(prev_permutation(vec.begin(), vec.end()));

이렇게 되면

결과물은 거꾸로 즉 내림차순 순열이 만들어집니다.

321, 312, 231, 213, 132, 123

이제 123 다음의 내림차순 배열은 다시처음으로 돌아온 321로 만들고 false를 반환합니다.

 

그렇기에 이것만 기억해주시면 됩니다.

순열 next_permutation 및 prev_permutation을 사용할 때에는 그에 맞는 오름차순, 내림차순 정렬을 해주신 다음 사용하는 것이 바람직 합니다.

 

끄으틍