C++ next_permutationソース分析

template<class _BidIt> inline
bool _Next_permutation(_BidIt _First, _BidIt _Last)
{ // permute and test for pure ascending, using operator<

//-----------------------------------------------\
_DEBUG_RANGE(_First, _Last);
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
   return (false);

//             

//-----------------------------------------------/

for (; ; )
   { // find rightmost element smaller than successor
   _BidIt _Next1 = _Next;
   if (_DEBUG_LT(*--_Next, *_Next1))
    { // swap with rightmost element that's smaller, flip suffix
    _BidIt _Mid = _Last;
    for (; !_DEBUG_LT(*_Next, *--_Mid); )
     ;
    std::iter_swap(_Next, _Mid);

//             ，               ，             ，    

//        ，                  ，      
    std::reverse(_Next1, _Last);

//    ，              
    return (true);
    }

   if (_Next == _First)
    { // pure descending, flip all
    std::reverse(_First, _Last);
    return (false);
    }
   }
}

重要なのは1つの配列の次の配列が何であるかを確定することで、私は見て理解しているが分からないと言って、そこで1段の転載をして、以下はhttp://www.cppblog.com/yindf/archive/2010/02/24/108312.html
abcd next_permutation->abdcでは、なぜabcdの次はacbdではなくabdcなのでしょうか.簡単に言えば、a,b,c,dの代わりに1,2,3,4を使って、元の配列の中間変換値1,2,3,4 3,2,1((3*(3)+2)*(2)+1)*(1)=23 1,2,4,3,2,0((3*(3)+2)*(2)+0)*(1)が得られる = 22 1,3,2,4         3,1,1             ((3 * (3) + 1) * (2) + 1) * (1) = 21 1,3,4,2         3,1,0             ((3 * (3) + 1) * (2) + 0) * (1) = 20 1,4,3,2         3,0,1             ((3 * (3) + 0) * (2) + 1) * (1) = 19 .                   .                      . .                   .                      . .                   .                      . 4,3,2,1         0,0,0             ((0 * (3) + 0) * (2) + 0) * (1) = 0                                |       |      |                       |                    |                   |                                |      |                              |                    |                                |                                     |
上記の中間変換とは、各数字の後ろに現在のビット数より大きい数字の個数を指す.例えば:1,3,4,2,1の後ろに(3,4,2)があります.彼らはみな1より大きいので、1位は3の後ろに(4,2)がありますが、4だけが3より大きいので、2位は1 4の後ろに(2)があり、4より大きいものはありません.だから3位が0の最後の位の後ろにはもっと大きくないに違いないので、0を省略しました.このような変換を経て、元の配列に対応して互いに変換できる表現(中間変換)が得られた.この中間表現をよく見ると、1位は(0,1,2,3)、2位は(0,1,2)、3位は(0,1,2)、(0,1).通常、数字は10進数で表され、コンピュータでは2進数で表されていますが、現在、私は特殊な進数で数を表しています.1位は1進数、2位は2進数です..そこで、この中間表現の10進数値が得られました.段|||1,1,0------>((1*(3)+1)*(2)+0)*(1)=8
3,1,0     ---->   ((3 * (3) + 1) * (2) + 0) * (1) = 20
これにより,1つの10進数と1つの配列との間の1つ1つの対応関係が得られる.
現在、配列数と秩序化された10進数は1つ1つ対応している(対応関係を変えることで、10進数を昇順させることができる).