[C++] STL - next_permutation

next_permutation

C++의 algorithm 헤더에 존재하는 next_permutation은 컨테이너에서 만들 수 있는 다음 순열을 반환하는 STL이다.

 

next_permutation 이용한 순열 구하기

int main() {
    int n, k;
    cin >> n >> k; // n개의 원소 중 k개 나열하는 순열

    vector<int> v;

    for(int i = 0; i < n; i++){
    	int x;
        cin >> x;
        v.push_back(x);
    }
        
    sort(v.begin(), v.end()); // 오름차순 정렬이 되어있어야함

    do {
        for(int i = 0; i < k; i++){
           cout << v[i] << " ";
		}
		cout << "\n";
    }while(next_permutation(v.begin(), v.end()));

    return 0;
}

 

next_permutation 이용한 조합 구하기

int main() {
    int n, k;
    cin >> n >> k; // n개의 원소 중 k개 선택하는 조합

    vector<int> v;

    for(int i = 0; i < n; i++){
    	int x;
        cin >> x;
        v.push_back(x);
    }
    
    vector<int> temp(v.size(), 1);
    for(int i = 0; i < k; i++){
    	temp[i] = 0;
    }
        
    sort(v.begin(), v.end()); // 오름차순 정렬이 되어있어야함

    do {
        for(int i = 0; i < v.size(); i++){
        	if(temp[i])
            	cout << v[i] << " ";
		}
		cout << "\n";
    }while(next_permutation(temp.begin(), temp.end()));

    return 0;
}

 

 

next_permutation을 이용하여 배열 s의 n개의 원소 중 k개를 선택하는 조합을 구하기 위한 방법은 다음과 같다.

1. 크기가 n인 배열 temp를 만들어 앞에서 부터 k개의 원소는 0, 나머지는 1로 초기화 해준다. 
2. temp의 모든 순열을 구한다
3. temp의 순열에서 원소값이 1인 인덱스만 배열 s에서 가져온다.

이때 next_permutation을 이용하면 순열이 오름차순으로 정렬되기 때문에, 조합은 내림차순으로 출력된다.

대신 prev_permutation을 이용하면 조합을 오름차순으로 출력할 수 있다.

prev_permutation은 내림차순 정렬된 데이터를 받아서 이전 순열로 바꿔준다.

따라서 이 경우는 temp를 앞에서부터 k개의 원소를 1, 나머지는 0으로 초기화 해야한다.

int main() {
    int n, k;
    cin >> n >> k; // n개의 원소 중 k개 선택하는 조합

    vector<int> v;

    for(int i = 0; i < n; i++){
    	int x;
        cin >> x;
        v.push_back(x);
    }
    
    vector<int> temp(v.size(), 0);
    for(int i = 0; i < k; i++){
    	temp[i] = 1;
    }
        
    sort(v.begin(), v.end()); // 오름차순 정렬이 되어있어야함

    do {
        for(int i = 0; i < v.size(); i++){
        	if(temp[i])
            	cout << v[i] << " ";
		}
		cout << "\n";
    }while(prev_permutation(temp.begin(), temp.end()));

    return 0;
}

---