STL next_permutation 간단 한 분석

오늘 은 전체 배열 의 비 재 귀적 실현 을 배우 고 싶 었 지만 반나절 동안 검색 해 보 았 는데 모두 전 재 된 같은 문장 이 었 다. 이 문장의 규칙 을 나 는 여전히 이해 하지 못 했다.
c + + 의 STL 에 next 가 있다 고 생각 합 니 다.permutation () 은 현재 시퀀스 보다 큰 다음 시퀀스 를 만 들 수 있 습 니 다.
이런 방법 을 통 해 전체 배열 의 비 재 귀적 실현 도 실현 할 수 있다.
 
STL 원본 다운로드:http://www.sgi.com/tech/stl/download.html
 
next_permutation () 의 원 함 수 는: stl 에 있 습 니 다.안에
내용 은 다음 과 같다.

// next_permutation and prev_permutation, with and without an explicitly 
// supplied comparison function.

template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
                 _LessThanComparable);
  if (__first == __last)
    return false;
  _BidirectionalIter __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  for(;;) {
    _BidirectionalIter __ii = __i;
    --__i;
    if (*__i < *__ii) {
      _BidirectionalIter __j = __last;
      while (!(*__i < *--__j))
        {}
      iter_swap(__i, __j);
      reverse(__ii, __last);
      return true;
    }
    if (__i == __first) {
      reverse(__first, __last);
      return false;
    }
  }
}

 
기본 사상 은 다음 과 같다.
마지막 으로 서로 인접 한 두 개 를 비교 하면 앞 에 있 는 것 이 뒤의 것 보다 작다 (i 는 작은 위치, ii, 비교적 큰 위치) 면 이때 반드시 하나의 배열 이 현재 의 것 보다 크다 는 것 이 존재 하고 그 다음 에 어떻게 다음 배열 이 생 길 수 있 습 니까?이 작은 수의 뒤 를 마지막 부터 그것 보다 큰 첫 번 째 수 를 찾 아 현재 작은 위치 로 바 꾼 다음 에 큰 수 ii 를 마지막 으로 역 순 으로 해 야 합 니 다.이렇게 해서 다음 배열 이 생 겼 다.원 리 는 다음 에 비교적 큰 것 을 시작 위치 로 하 는 수 를 찾 은 다음 에 뒤의 숫자 를 최소 부터 오름차 로 바 꾸 는 것 과 유사 하 다. 예 를 들 어 원래 4653 에서 5346 으로 바 꾸 는 것 이다.

next_permutation()
{
        if  no element || only one element
               return false;

        i = last_element_ptr
        while(true)
        {
                 ii = i;    // the element before i
                 --i;
                 if  *i < *ii   // then there must be a sequence to change
                 {
                        j =  last_element_ptr
                        while( !(*i<*--j)   //find the first element from tail to head
                        {}                      //which is bigger than *i
                        swap(i, j)            // swap the  elements which i and j point to.
                         reverse(ii, last_element_ptr)  // reverse the array
                        return true;
                }
                if i == first_element_ptr   // if we to the head of the array, so no permutation
                {
                        reverse(first_element_ptr, last_element_ptr)
                        return false
                 }
         }


}

 
      stl 의 nextpermutation 소스 코드 에서 우 리 는 이미 최대 가중치 의 서열 (즉, 현재 값 보다 큰 배열 이 없 음) 을 보 았 습 니 다. 반환 값 은 false 이지 만 서열 을 역 주 행 했 습 니 다. 예 를 들 어 4321 에 next 를 사용 합 니 다.permutation 후 서열 이 1234 로 바 뀌 었 습 니 다.
오 랜 시련 을 겪 은 소스 코드 를 읽 는 것 이 큰 도움 이 될 것 같다.
 
      이로부터 우 리 는 비 귀속 적 인 전체 배열 을 실현 할 수 있다.허허, 긴 말 할 필요 없 겠 지.