next_permutation/prev_permutation을 이용해 조합(Combination) 구하기

원리

전체 n개의 원소들 중에서 k개를 뽑는 조합(nCk)을 구한다면 n개의 벡터 원소에 1을 k개, 0을 나머지 n-k개 집어넣어서 순열을 돌리고 1에 해당하는 인덱스를 가져오면 된다.

 

Example

    a.push_back(1);
    a.push_back(1);
    a.push_back(0);
    a.push_back(0);

    for(int i = 1; i <= 4; ++i)
        num.push_back(i);
    do{
        for(int i = 0; i < num.size();i++){
            if(a[i] == 1)
                cout << num[i] << " ";
        }
        cout << endl;
    }while(prev_permutation(a.begin(),a.end()));