[Algorithm] 순열과 조합

참고한 블로그 : https://twpower.github.io/90-combination-by-using-next_permutation

#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;

}

<출력>

1 2 3 4 

1 2 4 3 

1 3 2 4 

1 3 4 2 

1 4 2 3 

1 4 3 2 

2 1 3 4 

2 1 4 3 

2 3 1 4 

2 3 4 1 

2 4 1 3 

2 4 3 1 

3 1 2 4 

3 1 4 2 

3 2 1 4 

3 2 4 1 

3 4 1 2 

3 4 2 1 

4 1 2 3 

4 1 3 2 

4 2 1 3 

4 2 3 1 

4 3 1 2 

4 3 2 1 

#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;

}

중복이 있는 경우에는 

0 1 1 과 같은 경우에도 중복을 제외하여 만들어줌

0 1 1 , 1 0 1, 1 1 0 의 세가지만 나옴. 

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

#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;

}