[C++] 순열 조합 알고리즘 구현하기

항상 궁금하면서 정리하지 못한 것 같아서, 정리하고 들어가기.

 

C++에서는 n개 중 k개를 뽑는 경우의 수를 구하는 라이브러리 next_permutation 이 있다.

이를 활용해서 순열 조합 문제를 해결할 수 있다.

단, 중요한 것은 순열 및 조합을 구하기 전에 sort 함수로 배열을 오름차순으로 정렬이 필요하다.

 

1) 순열

N개를 나열할 수 있는 경우의 수를 구한다.

#include <algorithm>

sort(v.begin(),v.end());

do {
        for(int i = 0; i < v.size(); i++){
           cout << v[i] << " ";
		}
		cout << "\n";

    }while(next_permutation(v.begin(), v.end()));

next_permutation은 algorithm 헤더에서 해당 값을 활용한다.

 

 

 

2) 조합

N개 중 k개를 뽑을 수 있는 경우의 수를 출력한다.

    
    // 0, 1을 넣어 임시 조합 생성
    vector<int> tempVector;
    
    // 선택 개수
    int n = 3;
 
    // 임시 벡터를 추가
    // 고를 경우 n개의 1을 추가
    for (int i = 0; i < n; i++)
        tempVector.push_back(1);
    //나머지는 다 0으로 초기화
    for (int i = 0; i < dungeons.size() - n; i++)
        tempVector.push_back(0);
        
    //해당 값을 sort하기
    sort(tempVector.begin(), tempVector.end());
    
    
    do{
    
        for (int i = 0; i < tempVector.size(); i++)
        {
            if (tempVector[i] == 1)
            { // 실제값 출력
                cout << dungeons[i][0] << " " << dungeons[i][1] << "\n";
            }
        }
 
        cout << endl;
        
    }while(next_permutation(tempVector.begin(),tempVector.end()));