[Algorithm] 순열 : 개념과 next_permutation

순열과 조합의 사용 상황

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

• {1,2,3} 중 2개 : {1,2}, {2,1}, {2,3}, {3,2}, {1,3}, {3,1}
• 순서를 재배치하여...~한 순서의 경우 max 값을...

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

• {1,2,3} 중 2개 : {1,2}, {2,3}, {1,3}

 

next_permutation (C++제공)

매개변수 : from(시작지점), to(끝지점 : to부분은 포함되지 않기 때문에 +1해줘야함) 

from ≤ 순열 < to

 

• 오름차순으로 정렬된 배열을 기반으로 순열을 만든다.

참고) prev_permutation (C++제공)

• 내림차순으로 정렬된 배열을 기반으로 순열을 만든다.

🎈 코드 예시

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a[] = {1, 2, 3};
    do
    {
        for (int i : a)
            cout << i << " ";
        cout << endl;
    } while (next_permutation(&a[0], &a[0] + 3));
}//(a,a+3)도 가능

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

 

만약 여기서 int a[] = {2,1,3}으로 하면 아래와 같이 모든 순열이 출력되지 않는다. 

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

주의) 배열(벡터)의 순열을 구하고 싶으면 항상 미리 sort를 해줘야한다 ! 

🎈 코드 예시(5개 중 2개를 선택할 때)

#include <bits/stdc++.h>

using namespace std;

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

중복되는건 단순히

1,2,3,100,200

1,2,3,200,100

등 나열이 될 때 2개씩 slice돼서 보이는 현상이다.

1 2 
1 2 
1 2 
1 2 
1 2 
1 2 
1 3 
1 3 
1 3 
1 3 
1 3 
1 3 
...
200 3 
200 100 
200 100 
200 100 
200 100 
200 100 
200 100 

 

참고) 순열의 공식

n개 중 r개 뽑기