순열(Permutation)

순서와 상관 O 뽑는다면 >> 순열

순서와 상관 X 뽑는다면 >> 조합

 

순서를 재배치하여 or 한 순서의 경우 max값을 어쩌구저쩌구 >> 순열

 

ex1)

[1, 2, 3] 3개를 뽑으라면 [1, 2, 3] => 조합(순서 상관 없음)

[1, 2, 3] 1번 부터뽑고 2번부터 뽑고 3번부터 뽑는다.

[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1] 총 6개 => 순열(순서 상관있음)

 

ex2)

[1, 2, 3] 2개를 순서 상관 없이 뽑으면

=> [1, 2], [2, 3], [1, 3] 3개

[1, 2, 3] 2개를 순서 상관 있이 뽑으면

=> [1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2] 6개

 

그럼 이것을 Code에서는 어떻게 진행을 할까?

C++에서는 이것을 사용할 수 있게 next_permutation이라는 순열 함수가 존재한다

next_permutation(from, to)

시작지점과 끝을 넣어주면 된다.

예를들어

[1, 2, 3]이라는 배열이 있을 때

1은 [0]번째

2는 [1]번째

3은 [2]번째로 설명할 수 있다.

from은 [0]번째를 넣어줘야 하며 to는 마지막번째 + 1번째의 자리를 넣어줘야 한다.

vector를 예로들면

vector<int> v_list = {1, 2, 3};

이런식으로 값이 들어가있다고 생각해보면

next_permutation(v_list.begin(), v_list.end());

이런식으로 사용하는 것이다.

 

next_permutation은 오름차순을 기준으로 순열을 만든다.

prev_permutation도 있는데 내림차순을 기준으로 순열을 만든다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    int a[] = {1, 2, 3};
    do
    {
        for (int i : a) cout << i << " ";
        cout << '\n';
    }while(next_permutation(&a[0], &a[0] + 3));
}

 

이 반복문을 모르시는 분들도(나 포함) 있을 것 같아 설명을 드리자면

for (int i : a)

 

 

이와 같이 C++17버전에서 사용하는 범위용 반복문이다

무언가 비슷한가 했더니

foreach(var item in arr)

범위용 C# 반복문이랑 똑같았다.

 

이해 가능해버렸다.

 

이제 여기서 do while문을 도는데 조건자체가

while(next_permutation(&a[0], &a[0] + 3));

이 next_permtation은 함수의 첫번째 인자로 순열을 구할 대상(map, array, vector 등)의 시작점 주소 혹은 iterator를, 두 번째 인자로는 끝나는 지점의 주소 혹은 iterator를 넘겨 받아 사용한다.

next_permutation은 배열을 순열로도 바꿔주지만 반환값은 true || false로 반환이 되는데

현재 순열이 사전 상에서의 마지막일 경우 true가 아닌 false를 반환한다.

 

※주의사항※

물론 이 것도 주의해야 할 사항은 받아오는 대상들이 오름차순으로 정렬이 되어 있어야 한다.

그렇지 않으면 현재 주어진 순열을 기준으로 사전 순의 다음 순열로 바꾸기 때문에 가능한 남은 경우의 수만 추출이 될 수도 있다.

 

ex)

[2, 1, 3] => [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1] 5개 나옴

[1, 2, 3] => [1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1] 원래 이게 제대로 나온거

 

그래서 이 순열 함수를 사용하기 전에 오름차순으로 정렬을 해주어야 한다.

#include <algorithm>

sort(a, a + 3);

 

이런식으로 말이다.

 

아무튼

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    int a[] = {1, 2, 3};
    do
    {
        for (int i : a) cout << i << " ";
        cout << '\n';
    }while(next_permutation(a, a + 3));
}

이런식으로 조건을 바꾸어서 넣어줄 수 있다.

애초에 배열에서 a에 담는 것은 시작점 주소 &a[0]이다.

그렇기에 &a[0] + 3은 a + 3이랑 마찬가지이다.

 

나도 옛날에 배웠는데 그랬던 것 같음 ㅇㅇ

 

vector 또한 똑같이 사용 가능하다.

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v_list = {1, 2, 3};
    do
    {
        for (int i : v_list) cout << i << " ";
        cout << '\n';
    }while(next_permutation(v_list.begin(), v_list.end()));
}

 

 

그러면 만약 조건을 바꿔보자.

 

5개의 원소가 들어있는 vector에 2개만 뽑아서 순서있게 나열하라고 하면 순열을 나타낸 것이다.

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v_list = {2, 1, 3, 100, 200};
    sort(v_list.begin(), v_list.end());
    
    do
    {
        for (int i = 0; i < 2; ++i)
        {
            cout << v_list[i] << " ";
        }
        cout << '\n';
    }while(next_permutation(v_list.begin(), v_list.end()));
}

 

이렇게 하면된다.

다만 출력하면

 

반복된다 반복

중복이 나온다.

이게 무슨 문제냐면

[1, 2, 3, 100, 200] 여기서 다음 순열을 만들 때

[1, 2, 3, 200, 100]

[1, 2, 100, 3, 200]  ... 이런식으로 순열이 만들어질 것이다.

 

여기서 2개만 출력하니 중복된것처럼 보이는것이다.

 

이제

저승시작

 

 

여기서 공식을 알아가자

P는 Permutation의 약자로 사용한다.

nPr = n! / (n-r)!

 

이게 순열 공식이다.

 

여기서 n과 r은 무슨뜻이냐면 n개중에 r개를 뽑는다는 이야기이다.

예를 들어 3개중에 1개를 뽑는다?

3P1이다.

만약 2개를 뽑으면

3P2이다.

이해갔나?

그러면 3P2 = 3! / (3-2)!인 것이다. 그러면 3! / (3-2)!는 (3-2)!가 1인 것이니 결국 3!란 것이다.

그러면 총 3x2x1 = 6이기 때문에 6개가 나오는 것이다.

 

수학무서워..