0주차-2. 기초 개념 : 순열(Permutation)

순열이란?

• 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음)
• 1, 2, 3이라는 수들의 집합이 있을 때
• {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 이렇게 6가지 순열이 나온다.

n P r이란, 쉽게 말해 n개중에 r개로 이루어진 수열을 만든다는 뜻.

 

 

---

 

 

 

 

 

프로그램에서 구현 방법은?

• do-while문을 이용한 구현

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

template<typename T>
void print(const T& container)
{
	for (auto e : container)
		std::cout << e << " ";
	std::cout << std::endl;
}
int main()
{
	std::vector<int> v{ 1, 2, 3, 4, 5 };
	do
	{
		print(v);
	} while (std::next_permutation(std::begin(v), std::end(v)));
}

• std::next_permutation(begin, end)를 통해 v내의 원소를 섞어주고 모든 순열을 순회

 

 

---

• 재귀 함수를 이용한 구현

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

template<typename T>
void print(const T& container)
{
	for (auto e : container)
		std::cout << e << " ";
	std::cout << std::endl;
}


std::vector<int> v{ 1, 2, 3 };
void makePermutation(int n, int r, int depth)
{
	if (r == depth)
	{
		print(v);
		return;
	}

	for (int i = depth; i < n; i++)
	{
		std::swap(v[i], v[depth]);
		makePermutation(n, r, depth + 1);
		std::swap(v[i], v[depth]);
	}

	return;
}


int main()
{
	makePermutation(3, 3, 0);

	//do
	//{
	//	print(v);
	//} while (std::next_permutation(std::begin(v), std::end(v)));
}

• 재귀 함수의 흐름은 반드시 2번 이상 도식화 연습을 해야 한다.