STL 소스 학습 --- nextpermutation 과 prevpermutation 알고리즘

STL 에서 도 교체 기 범위 내 배열 알고리즘 을 제공 합 니 다. nextpermutaion 과 prevpermutation 즉.본 고 는 먼저 흔히 볼 수 있 는 문자열 의 전체 배열 알고리즘 을 제시 한 다음 에 STL 이 제공 하 는 next 를 분석 하고 자 한다.permutation 과 prevpermutation 알고리즘.
 
1. 무 거 운 문자열 의 전체 배열 알고리즘
문자열 전체 배열 에서 이 문자열 에 같은 두 요소 가 존재 한다 면 이 문자열 의 전체 배열 개 수 는 n 이 아 닙 니 다!그래서 같은 원소 의 상황 을 고려 해 야 한다.아래 의 실현 은 교환 하 는 사상 을 이용 하여 문자열 의 전체 배열 알고리즘 을 재 귀적 으로 해석 하 는 것 이다.

 1 void swap(char* x, char* y)  2 {  3     char tmp;  4     tmp = *x;  5     *x = *y;  6     *y = tmp;  7 }  8 

 9 void permute(char *str, int i, int n) 10 { 11    int j; 12 

13    if (i == n) 14      printf("%s
", str); 15    else{ 16         for (j = i; j <= n; j++){ 17           if(str[i] == str[j] && j != i)  //         ，             

18             continue; 19           swap((str+i), (str+j)); 20           permute(str, i+1, n); 21           swap((str+i), (str+j)); 22  } 23  } 24 }

위의 코드 는 permite (str, 0, len) 호출 을 통 해 str 의 0 ~ len 의 전체 배열 을 계산 할 수 있 습 니 다.
 
2，next_permutation 과 prevpermutation 알고리즘
next 이해permutation 과 prevpermutation, 먼저 전체 배열 중의 '다음 전체 배열' 이 무엇 인지, '이전 전체 배열' 이 무엇 인지 보 세 요.세 글자 로 구 성 된 서열 {a, b, c} 을 고려 하면 이 서열 의 전체 배열 은 abc, acb, bac, bca, cab, cba 등 6 개의 요소 가 있다.위의 6 조 요 소 는 사전 순서에 따라 정렬 되 어 있다.acb 는 abc 의 다음 전체 배열 입 니 다. 마찬가지 로 cab 는 cba 의 이전 전체 배열 입 니 다.
 
  2.1 next_permutation 의 실현
       next_permutation 의 실현 과정 은 다음 과 같다.
         먼저, 맨 끝 에서 앞으로 두 개의 인접 한 요 소 를 찾 습 니 다. 첫 번 째 요 소 는 i 이 고 두 번 째 요 소 는 ii 이 며 i < ii 를 만족 시 킵 니 다.
         그 다음 에 맨 끝 에서 앞으로 검색 하여 첫 번 째 i 이상 의 요 소 를 찾 아 j 로 설정 합 니 다.
         그리고 i 와 j 를 대조 하고 ii 와 그 뒤의 모든 요 소 를 반전 시 킵 니 다.
         이렇게 얻 은 새로운 서열 은 바로 '다음 배열' 이다.
         다음은 nextpermutation 의 상세 한 실현:

 1 template <class _BidirectionalIter>

 2 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {  3  __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);  4   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,  5  _LessThanComparable);  6   if (__first == __last) //     ，  false  7     return false;  8   _BidirectionalIter __i = __first;  9   ++__i; 10   if (__i == __last) //          ，  false 11     return false; 12   __i = __last; 13   --__i; 14 

15   for(;;) { 16     _BidirectionalIter __ii = __i; 17     --__i; 18     if (*__i < *__ii) { //       i,ii 19       _BidirectionalIter __j = __last; 20       while (!(*__i < *--__j)) // j 21  {} 22  iter_swap(__i, __j); //  i,j 23  reverse(__ii, __last); // [ii,last)         24       return true; 25  } 26     if (__i == __first) { //       ，，                        27  reverse(__first, __last); //        28       return false; 29  } 30  } 31 }

         2.2 prev_permutation 의 실현
   　　prev_permutation 의 실현 과정 은 다음 과 같다.
              먼저, 맨 끝 에서 앞으로 두 개의 인접 한 요 소 를 찾 아 첫 번 째 요 소 는 i 이 고 두 번 째 요 소 는 ii 이 며 i > ii 를 만족 시 킵 니 다.
              그리고 맨 끝 부터 i 보다 작은 요 소 를 찾 아 j 로 만 듭 니 다.
              그리고 i 와 j 를 대조 하고 ii 와 그 후의 모든 요 소 를 반전 시 킵 니 다.
             이렇게 얻 은 서열 은 바로 이 배열 의 이전 배열 이다.

 1 template <class _BidirectionalIter>

 2 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {  3  __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);  4   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,  5  _LessThanComparable);  6   if (__first == __last)  7     return false;  8   _BidirectionalIter __i = __first;  9   ++__i; 10   if (__i == __last) 11     return false; 12   __i = __last; 13   --__i; 14 

15   for(;;) { 16     _BidirectionalIter __ii = __i; 17     --__i; 18     if (*__ii < *__i) { //      ii<i    19       _BidirectionalIter __j = __last; 20       while (!(*--__j < *__i)) // j 21  {} 22  iter_swap(__i, __j); //  i j 23  reverse(__ii, __last); //  [ii,last)       24       return true; 25  } 26     if (__i == __first) { //               i,                  27  reverse(__first, __last); //       ，   false 28       return false; 29  } 30  } 31 }