[c++] next_permutation 조합 구하기

[1, 2, 3, 4] 를 이용하여 네 자리 수 조합 만들기

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    vector<int> v;
 
    for (int i = 0; i < 4; i++)
    {
        v.push_back(i + 1);
    }
 
    sort(v.begin(), v.end());
 
    do
    {
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
        }
 
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
 
    return 0;
}

---------------------------------------------

n개의 원소들 중 k개의 조합 구하기 (= nCk 구하기)

 

k 개의 원소에 1을, n-k 개의 원소에 0을 넣어 만든 조합을 만들어, 원소가 1인 인덱스에 해당하는 값을 가져오면 된다.

ex ) [1 2 3 4 5 6] 이고 [0 0 1 1 1 1] 이면 원하는 결과는 [3 4 5 6] 이다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n = 6;
    int k = 4;
 
    vector<int> v;
 
    for (int i = 0; i < n; i++)
    {
        v.push_back(i + 1);
    }
 
    // 0, 1을 넣어 임시 조합 생성
    vector<int> tempVector;
 
    for (int i = 0; i < k; i++)
    {
        tempVector.push_back(1);
    }
 
    for (int i = 0; i < v.size() - k; i++)
    {
        tempVector.push_back(0);
    }
 
    sort(tempVector.begin(), tempVector.end());
 
    do
    {
        for (int i = 0; i < tempVector.size(); i++)
        {
            if (tempVector[i] == 1)
            { // 실제값 출력
                cout << v[i] << " ";
            }
        }
 
        cout << endl;
 
    } while (next_permutation(tempVector.begin(), tempVector.end()));
 
    return 0;
}