오늘의 공부

Permutation

순열

◎ 수학에서 순열 구하기

n개에서 r개를 택하는 순열이란 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것이다. 

여기서 중요한 것은 '순서 있게'다. 왜냐하면 개념이 헷갈리는 조합은 '순서'가 없이 나열하는 것이기 때문에 구분을 잘 해야 한다. 

표현은 주로 nPr로 한다. (n개에서 r개를 택하는 Permutation)

이 순열을 구하는 방법은 간단하다. 바로 팩토리얼을 이용하면 된다.

식을 간단하게 표현하면 위와 같다. 

◎ Permutation 사용

순열을 구하기 위해서는 재귀를 통해서 직접 구현할 수도 있다. 하지만 stl에 있는 기능을 가져다가 사용하면 빠르고 간단하게 순열을 만들 수 있다.

std::prev_permutation과 std::next_permutation은 현재 범위가 현재보다 더 작은 순열(이전 순열) 또는 더 큰 순열(다음순열)이 되도록 요소들을 정리한다. 이전 순열이나 다음 순열이 있으면 true, 없으면 false를 리턴한다. 

이때 순열이 끝나 false를 리턴하는 경우는 완전히 역순이 되는 경우다. 이 때 다시 원래 순서대로 바꾼뒤에 false를 리턴하는 것이다. 

ex) 1234의 경우 return 하기 직전 4321였다가 false를 리턴할때 다시 1234로 만들어준다. 

단 permutation은 중복이 있는 경우에는 중복을 제외하고 순열을 만들어준다. 

permutation 기능의 원리는 다음과 같다.

1. 우선 뒤에서부터 탐색을 시작한다. 오름차순의 형태를 띄는 구간이 나올 때까지 진행하며 작은 쪽은 i, 큰 쪽은 ii라고 가정한다. 

2. 그 다음에는 뒤에서부터 i보다 큰 j를 찾아 i와 j를 바꿔준다.

3. 그 후 ii를 포함해 뒷부분을 모두 reverse한다. 

범위를 이전 순열로 만드는 것

범위를 다음 순열로 만드는 것

위의 인자에 정렬 기준을 명시적으로 사용할 수 있다. 기본적으로는 std::less가 사용된다.

두 알고리즘 중 어떤 것을 사용하든, 주어진 범위의 모든 순열을 손쉽게 생성할 수 있다. 

ex ) permutation을 사용한 예시 

#include <algorithm>

std::vector<int> Init{1,2,3};
do{
	for(auto i:Init) std::cout << i;
	std::Cout << " ";
} while(std::next_permutation(Init.begin(), Init.end())); 

// 출력 예시 123 132 213 231 312 321 

std::reverse(Init.begin(), Init.end());
do{
	for(auto i:Init) std::cout << i;
    std::cout << " ";
 } while(std::prev_permutation(Init.begin(), Init.end()));
 
 // 출력 예시 321 312 231 213 132 123

permutation말고 직접 순열 구하기? 

참고 자료;

namu.wiki/w/%EC%88%9C%EC%97%B4

핵심 C++ 표준 라이브러리 (라이너 그림 지음; 류광 옮김. 인사이트) 

jeonggyun.tistory.com/110