[알고리즘] 순열과 조합 c++ 구현

목차

 

c++로 순열과 조합을 어떻게 구현하는지에 대해 알아보자

 

stl로 구현한 순열

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	sort(v.begin(), v.end());  //순열을 만들때는 정렬을 해주어야함
	do {
		for (int i : v) cout << i << " ";
		cout << '\n';

	} while (next_permutation(v.begin(), v.end() ));   //오름차순으로 만들어줌
    
    do {
		for (int i : v) cout << i << " ";
		cout << '\n';

	} while (prev_permutation(v.begin(), v.end() ));   //내림차순으로 만들어줌

}

 

재귀함수로 구현한 순열

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

void printV(vector<int>& v) {   //순열 출력 함수
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n";
}

void makePermutation(int n, int r, int depth) {
	cout << n << ":" << r << ":" << depth << '\n';  //과정을 보기위한 출력
	if (r == depth) {   //순열 출력
		printV(v);
		return;
	}
	for (int i = depth; i < n; i++) {
		swap(v[i], v[depth]);
		makePermutation(n, r, depth + 1);
		swap(v[i], v[depth]);  //귀 호출이 끝난 후에는 다시 이전의 상태로 복구해야 합니다. 
		//따라서 이전에 교환한 요소들을 다시 원래의 위치로 되돌려줍니다.
	}
	return;
}


int main()
{
	vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	sort(v.begin(), v.end());
	makePermutation(3, 3, 0);  
}

 

재귀함수로 구현한 조합

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int n = 5, k = 3;
void print(vector<int>& v) {
	for (int i : v)cout << i << " ";
	cout << "\n";
}

void combi(int start, vector<int> b) {
	if (b.size() == k) {
		print(b);
		return;
	}
	for (int i = start + 1; i < n; i++) {
		b.push_back(i);
		combi(i, b);
		b.pop_back();
	}
}



int main()
{
	vector<int>b;
	combi(-1, b);

}

 

3중 for문으로 구현한 조합

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int n = 5, k = 3;

int main()
{
	int i, j, k;
	vector<int>b;
	for (i = 0; i < n; i++) {
		b.push_back(i);
	}
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			for (k = j + 1; k < n; k++) {
				cout << b[i] << " " << b[j] << " " << b[k]<<"\n";
			}
		}
	}

}