C++ next_permutation的STL源碼解析

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    if (first == last) {
        return false;
    }
    
    BidirectionalIterator i = last;
    if (first == --i) {
        return false;
    }
    
    while (true) {
        BidirectionalIterator i1, i2;
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            iter_swap(i, i2);
            reverse(i1, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

next_permutation函數的實現是基于C++標準庫algorithm頭文件中的一個模板函數。該函數接受兩個迭代器參數，表示一個范圍，并將該范圍中的元素調整為下一個排列。

函數首先判斷范圍是否為空，若為空則返回false。然后初始化迭代器i指向最后一個元素的位置，若范圍只有一個元素，則返回false。接下來進入一個循環，不斷比較相鄰元素，直到找到一個位置i，使得*(i-1) < *i。然后在剩余范圍中找到一個位置i2，使得*i < *i2，交換i和i2位置的元素，再將i1到末尾的元素翻轉，即得到下一個排列。

如果無法找到位置i，則翻轉整個范圍，并返回false。

這段代碼基于STL的迭代器概念，通過比較元素大小和交換位置來實現下一個排列的生成。