C++ - 순열(Permutation), 조합(Combination)

재귀함수 연습

순열(Permutation)

 

1.

#include <iostream>

using namespace std;

void swap(char & a, char & b)
{
	char temp = a;
	a = b;
	b = temp;
}

void permutation(char data[], int depth, int n, int r)
{
	if (depth == r)
	{
		for (int i = 0; i < r; i++)
		{
			cout << data[i];
		}
		cout << endl;

		return;
	}

	for (int i = depth; i < n; i++)
	{
		swap(data[i], data[depth]);
		permutation(data, depth + 1, 4, 4);
		swap(data[i], data[depth]);
	}
}

int main()
{
	char arr[] = { 'a', 'b', 'c', 'd' };
	permutation(arr, 0, 4, 3); // 4P3

	return 0;
}

2.

#include <iostream>
#include <vector>

using namespace std;

void repeatPermutation(vector<pair<char, bool>> check, vector<char> perm, int depth)
{
	if (depth == perm.size())
	{
		for (int i = 0; i < perm.size(); i++)
		{
			cout << perm[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = 0; i < check.size(); i++)
	{
		if (check[i].second == true) continue;

		check[i].second = true;
		perm[depth] = check[i].first;
		repeatPermutation(check, perm, depth + 1);
		check[i].second = false;
	}
}

int main()
{
	const int p = 3;
	vector<char> word = { 'a', 'b', 'c', 'd' };
	vector<char> perm(p);
	vector<pair<char, bool>> check;

	for (int i = 0; i < word.size(); i++)
	{
		check.push_back(make_pair(word[i], false));
	}

	repeatPermutation(check, perm, 0);

	return 0;
}

3. STL 사용 next_permutation

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

using namespace std;

int main(){

	vector<char> v = {'a', 'b', 'c', 'd'};
	const int r = 3;

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

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

}

 

실행결과

 

조합(Combination)

1.

#include <iostream>
#include <vector>

using namespace std;

void Combination(vector<pair<char, bool>> check, vector<char> perm,int index, int depth)
{
	if (depth == perm.size())
	{
		for (int i = 0; i < perm.size(); i++)
		{
			cout << perm[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = index; i < check.size(); i++)
	{
		if (check[i].second == true) continue;

		check[i].second = true;
		perm[depth] = check[i].first;
		Combination(check, perm, index + 1, depth + 1);
		check[i].second = false;
	}
}

int main()
{
	const int p = 3;
	vector<char> word = { 'a', 'b', 'c', 'd' };
	vector<char> perm(p);
	vector<pair<char, bool>> check;

	for (int i = 0; i < word.size(); i++)
	{
		check.push_back(make_pair(word[i], false));
	}

	Combination(check, perm, 0, 0);

	return 0;
}

2. STL 사용 prev_permutation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    const int r = 3;
    
    vector<char> arr{'a', 'b', 'c', 'd'};
    vector<bool> temp(arr.size(), false);
    for(int i = 0; i < r; i ++) // 앞부터 r개의 true가 채워진다. 나머지 뒤는 false.
        temp[i] = true;
 
    do {
        for (int i = 0; i < arr.size(); ++i) {
            if (temp[i])
                cout << arr[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));
}

 

next_permutation 은 현재부터 오름차순으로

prev_permutation 은 현재부터 내림차순으로 정렬해주는 STL 함수로 여러곳에서 활용가능할듯하다