[필수 개념] 순열 / 조합

∙ 순열

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

ex) 문제에서 순서를 재배치하여....~한 순서의 경우 max 값

// 순열

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int a[] = {1, 2, 3};
    sort(a,a+3);
    
    do{
        for(int i : a)
            cout << i << " ";
        cout << '\n';
    }while(next_permutation(&a[0],&a[0] + 3)); // next_permutation : 오름차순기반으로 순열 만듬
    
    
    // 백터를 사용했을 때
    vector<int> b = {1, 2, 3};
    sort(b.begin(), b.end());
    do{
        for(int i = 0; i < 2; i++)  // 두개를 뽑아 순열 만듬
            cout << b[i] << " ";
        cout << '\n';
    }while(next_permutation(b.begin(), b.end()));
}

 

∙ 재귀함수로 만드는 순열

// 재귀함수로 만드는 순열

#include <iostream>
#include <vector>

using namespace std;
vector<int> v;

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

void makePermutation(int n, int r, int depth){
    cout << n << " : " << r << " : " << depth << '\n';
    if (r == depth){
        printV(v);
        return;
    }
    for (int i = depth; i < n; i++){
        swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
}


int main()
{
    for(int i = 1; i <= 3; i++){
        v.push_back(i);
    }
    makePermutation(3,3,0);
}

 

∙ 조합

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

ex) 순서 상관없이 "다양하게" 몇명을 뽑을 때

// 재귀함수로 만드는 조합 (4개이상은 재귀함수가 좋음, 3개 이하는 중첩 반복문)

#include <iostream>
#include <vector>

using namespace std;

int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};

void printV(vector<int> b){
    for (int i : b)
        cout << i << " ";
    cout << '\n';
}

// 외우셈,,,,
void combi(int start, vector<int> b){
    if (b.size() == k){
        printV(b);
        return;
    }
    for (int i = start + 1; i < n; i++){
        b.push_back(i); // index 기반으로 뽑는게 좋음
        combi(i, b);
        b.pop_back(); // 원복
    }
}

int main()
{
    vector<int> b;
    combi(-1, b);
}