[C++] 순열과 조합

1. 조합

STL함수 next_permutation을 활용한 조합 구현

void combinationSTL(vector<int> set, int n, int r) {
	for (int j = 0; j < n - r; ++j)
		set.push_back(0);
	for (int j = 0; j < r; ++j)
		set.push_back(1);
	do {
		for (int j = 0; j < n; ++j)
			if (set[j])
				printf("%d ", j);
		printf("\n");
	} while (next_permutation(set.begin(), set.end()));
}

 

재귀함수를 활용한 조합 구현

#include<iostream>
 
#define MAX 5
using namespace std;
 
int Arr[MAX];
bool Select[MAX];
 
void Print()
{
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true)
        {
            cout << Arr[i] << " ";
        }
    }
    cout << endl;
 
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 3)
    {
        Print();
        return;
    }
 
    for (int i = Idx; i < MAX; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;

        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}

2. 순열

STL함수 next_permutation을 활용한 순열 구현

/*
순열은 초기화가 필요하다.
for (int i = 0; i < n; ++i)
		set.push_back(i);
*/
void permutationSTL(vector<int> set, int n, int r) {
	do {
		for (int i = 0; i < r; ++i)
			printf("%d ", set[i]);
		printf("\n");
	} while (next_permutation(set.begin(), set.end()));
}

 

재귀함수를 활용한 순열 구현

#include<iostream>
#include<vector>
 
#define MAX 5
using namespace std;
 
int Arr[MAX];
bool Select[MAX];
vector<int> V;
 
void Print()
{
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}
 
void DFS(int Cnt)
{
    if (Cnt == 3)
    {
        Print();
        return;
    }
 
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        V.pop_back();
        Select[i] = false;
    }
}

 

순열과 조합의 재귀 코드를 완전히 이해하는 것은 시간이 걸릴 듯 하다..

오늘은 전반적인 코드 이해로 만족해야겠다.

 

 

참고 블로그 : https://yabmoons.tistory.com/100?category=838490