[Algorithm] C++에서 next_permutation을 이용해 조합(Combination) 구하기

C++의 next_permutation 함수를 이용해서 조합을 만들어보자

환경 및 선수조건


next_permutation 함수

기본 사용법

위 링크를 통해서 더 자세하게 볼 수 있지만 간단하게나마 정리하고 갑니다.

example.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main (){

	vector<int> v;

	// 1부터 4까지 대입
	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++){
			printf("%d ", v[i]);
		}

		printf("\n");

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

	return 0;

}


중복이 있는 원소들의 경우

중복이 있는 원소의 경우 중복인 경우를 제외하고 순열을 만들어줍니다. 즉, 예를 들어서 0 1 1이 있다면 아래와 같은 경우만 순열을 출력해줍니다.

0 1 1
1 0 1
1 1 0

example.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main (){

	vector<int> v;

	// 0 1 1 대입
	v.push_back(0);
	v.push_back(1);
	v.push_back(1);

	// 정렬
	sort(v.begin(), v.end());

	//순열
	do{
		// 출력
		for(int i=0; i<v.size(); i++){
			printf("%d ", v[i]);
		}

		printf("\n");

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

	return 0;

}


next_permutation을 이용해 조합(Combinataion) 구하기

원리

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


코드

1부터 6까지의 수 중에서 4개를 뽑아서 조합을 만들어보자.

example.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main (){

	// 1부터 6까지 담을 벡터
	vector<int> n;

	// 1부터 6까지 생성
	for(int i=0; i<6; i++){
		n.push_back(i+1);
	}

	// 0과1을 저장 할 벡터 생성
	vector<int> ind;

	// k=4, 4개를 뽑으니까
	int k = 4;

	// k개의 1 추가
	for(int i=0; i<k; i++){
		ind.push_back(1);
	}

	// 2개(6개-2개)의 0 추가
	for(int i=0; i<n.size()-k; i++){
		ind.push_back(0);
	}

	// 정렬
	sort(ind.begin(), ind.end());

	//순열
	do{
		// 출력
		for(int i=0; i<ind.size(); i++){
			if(ind[i] == 1){
				printf("%d ", n[i]);
			}
		}

		printf("\n");

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

	return 0;

}

구현 결과

3 4 5 6
2 4 5 6
2 3 5 6
...
1 2 3 6
1 2 3 5
1 2 3 4


참고자료

  • 코드플러스 알고리즘 중급 강의

[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading