c++에서 순열과 조합 구하기 (next_permutation, prev_permutation)

 

순열과 조합

순열은 순서가 상관이 있는 수의 집합이다.

순열에서는 {1,2,3}과 {2,1,3}이 다르다.

 

조합은 순서가 상관이 없는 수의 집합이다.

조합에서는 {1,2,3}과 {2,1,3}이 같다.

 

이번에는 next_permutation과 prev_permutation으로 순열과 조합을 구해볼 것이다.

https://tose33.tistory.com/149

c++) next_permutation, prev_permutation

 

위 함수를 사용하지 않고 백트래킹과 DFS로 직접 구하는것은 다른 글에서 다룬다.

 

- 추가: next_permutation 은 중복 결과는 제외된다.

예를들어 "aab" 를 돌리면 

{aab, aba, aab, aba, baa, baa} 가 아닌

{aab, aba, baa} 가 결과다. 

---

순열

 

{1,2,3,4}의 모든 순열을 구한다. 

{1,2,3,4}의 배열을 만들어서 그냥 permutation 함수를 돌리면 모든 순열을 구할수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int arr[5];

    // 1,2,3,4
    for(int i = 1; i <= 4; i++) {
        arr[i] = i;
    }

    do {
        for(int i = 1; i <= 4; i++) {
            cout << arr[i] << ' ';
        }
        cout << endl;
    } while(next_permutation(arr+1, arr+4+1)); // 인덱스 1부터 시작이므로 마지막 요소는 +5에있음

}

 

출력:

 

---

조합

 

순열은 순서가 상관이 있으므로 permutation을 돌리는 족족 모두 출력했다.

그냥 arr[] = {1,2,3,4} 를 permutation 함수로 돌리면 모든 순열을 구할수 있었다.

 

조합은 조금 다르다.

조합은 순서가 상관이 없다. 

즉 {1,2,3,4}와 {1,2,4,3}이 같은 집합인 것이다. 

따라서 조합은 mark[] 배열을 따로 만들어서 해당 숫자를 출력해도 될지 확인을 해줘야한다. 

 

수열 {1,2,3,4,5,6} 에서 4개를 뽑아 조합을 만든다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int arr[7];
    int mark[7];

    for(int i = 1; i <= 6; i++) {
        arr[i] = i;
    }

    // 6개중 4개를 뽑을 것이므로
    // mark[] = {1 1 1 1 0 0 0}
    for(int i = 1; i <= 6; i++) {
        if(i <= 4)
            mark[i] = 1;
        else
            mark[i] = 0;
    }

    do {
        for(int i = 1; i <= 6; i++) {
            // mark[i]가 1인 경우에만 arr[i]를 출력한다 
            if(mark[i] == 1)
                cout << arr[i] << ' ';
        }
        cout << endl;
    } while(prev_permutation(mark+1, mark+7));
}

 

출력:

 

mark[] 배열을 출력해보면 다음과 같다: