Permutation: 정렬된 수열에서 조합 뽑기

[devLupin]

Permutation

---

• #include <algorithm>
• 원래 벡터 값은 마지막에 바뀐 수열 값으로 저장된다.
  • 예를들어, n+2번째 permutation에서 멈췄다면,
  • vector v는 n+2번째 조합으로 저장되어 있다.

01. next_permutation(iter.begin(), iter.end())

• 오름차순으로 정렬된 수열의 모든 조합 추출

02. prev_permutation(iter.begin(), iter.end())

• 내림차순으로 정렬된 수열의 모든 조합 추출

03. usage

#include <algorithm>
using namespace std;

vector<int> a, b;    // a는 오름차순, b는 내림차순 정렬로 가정

do {
        for(int n : a)  cout << n << ' ';
} while (next_permutation(a.begin(), a.end()));

do {
        for(int n : b)  cout << n << ' ';
} while (prev_permutation(b.begin(), b.end()));

[devLupin]

• 조합(Combination) : n개의 원소 중에서 r개를 뽑는 경우의 수
• 오름차순으로 정렬된 원소들을 오름차순의 조합으로 출력하기 위해서는 prev_permutation
  • next_permutation은 오름차순으로 정렬되기 때문에 조합은 내림차순으로 출력

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
    vector<int> num{ 1,2,3,4 };
    vector<int> tmp{ 1,1,0,0 };

    do {
        for (int i = 0; i < num.size(); i++)
            if (tmp[i] == 1) cout << num[i] << ' ';
        cout << '\n';
    } while (prev_permutation(tmp.begin(), tmp.end()));

    return 0;
}