next_permutation / pre_permutation

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가지가 나오게 된다.

c++ STL에서는 순열을 정렬하는 함수로 next_permutation과,prev_permutation이 있다.

algorithm 헤더파일을 추가하여(#include<algorithm>)순열을 구할 수 있다.

next_permutation

기본 구조

코드

1,2,3,4 4가지의 원소를 입력받았다고 했을때,

출력값

pre_permutation

기본구조

주의할 사항

1. next_permutation과 pre_permutation의 차이는 순열을 구할 데이터의 정렬(오름차순)의 유무이다.
   next_permutation는 오름차순으로 정렬되어있어야하고,
   pre_permutation는 내림차순으로 정렬되어 있어야 한다.

2. 중복이 있는 원소들은 중복을 제외하고 순열을 만들어 준다.
   예를 들어,{1,1,2}과 같은 배열의 순열을 구하면,
   {1,1,2},{1,2,1},{2,1,1}이 된다.