[C++] 순열 구하기

도움받은 사이트 : 나무위키 (https://namu.wiki/w/%EC%88%9C%EC%97%B4(%EC%88%98%ED%95%99))

 

개요 :

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

 

ex) 4개의 원소 : 1, 2, 3, 4

이중 2개를 골라 나열하면, n = 4, r = 2.

 

1 2

1 3

1 4

2 1

2 3

2 4

3 1

3 2

3 4

4 1

4 2

4 3

 

C++ 에선 STL 에 next_permutation 이란 함수가 있지만 위와 같이 nPr 타입을 지원하진 않는다.

이에 위와 같이 nPr 타입의 순열을 출력하는 함수를 간단히 구현해 보았다.

 

(Warning : 처음 초기값이 오름차순으로 입력되어야 한다. 1,2,3,5,8 ~~~ 등 )

 

reverse() 함수도 STL 에서 제공하는 함수이다.

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <cstdio>   #include <vector> #include <algorithm>   using namespace std ;   int permutation(int n, int r) {         vector<int>             vecInt ;         vector<int>::iterator   vecIntIter ;           for(int ii = 1; ii <= n; ii++)                 vecInt.push_back(ii) ;           while(1)         {                 for(int ii = 0; ii < r; ii++)                         printf("%d ", vecInt[ii]) ;                 printf("\n") ;                   reverse(vecInt.begin() + r, vecInt.end()) ;                   if(!next_permutation(vecInt.begin(), vecInt.end()))                         break ;         }           return 1 ; }     int main() {         permutation(4, 2) ;           return 1 ; }

 

위 실행으로 순열 결과는 얻었지만 응용하기엔 애매하다.

 

이에 아래와 같이 살짝 변형하였다.

 

permutation() 함수의 vector<int>* 부분은 템플릿을 사용하여 일반화시킬 수 있지만

가독성이 떨어져 특정 타입으로 선언하였다.

 

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <cstdio>   #include <vector> #include <algorithm>   using namespace std ;   int permutation(vector<int>* vecInt, int r) {         reverse(vecInt->begin() + r, vecInt->end()) ;         return next_permutation(vecInt->begin(), vecInt->end()) ; }     int main() {         vector<int>             vecInt ;         vector<int>::iterator   vecIntIter ;           int n = 4 ;         int r = 2 ;           for(int ii = 1; ii <= n; ii++)                 vecInt.push_back(ii) ;           while(1)         {                 for(int ii = 0; ii < r; ii++)                         printf("%d ", vecInt[ii]) ;                 printf("\n") ;                   if(!permutation(&vecInt, r))                         break ;         }           return 1 ; }