大神的世界

字典排序 ( next_permutation (不是中翻英 = = , 請看程式碼))

if( list[ i-1 ] < list [ i ] )  如果都沒發生，則 list 為大到小排序 (最大了)

那為什麼要找 list[ i-1 ] < list[ i ] 呢？

因為 list[ i ] 之後為大到小，把這些數往前移只會讓整體變得更小而已

因此，如果要找下一個比較大的數

就得將 list[ i-1 ] 換成一個稍稍大的數

多大呢？

就 list[ i ] 之後比他大且最靠近他的數 (姑且稱作 list[ j ] )

因為 list[ i ] 後為大到小，所以我們就從最後面往前找出第一個比他大的數

交換後

list[ i ] 後仍為大到小，但 list[ i ] 前比交換前稍稍大了

但這並不是下一個數，因為 list[ i ] 之後是大到小

因此，我們將 list[ i ] 之後 reverse 變成小到大

則這個數就是我們要找的稍稍大的數  

ex:

23651  (下一個數應為 25136 )

list[ i ] = 6

list[ j ] = 5

swap( &list[ i-1 ] , &list[ j ] )

得到 25631

reverse(&list[ i ], &list[ len(list) ] )

得到 25136

#include <iostream>
#include <algorithm>

using namespace std;

string next_permutation(string list, const int len)
{
    for (int i=len-1; i>0; i--)
        if (list[i-1] < list[i])
        {
            int j = len-1;
            while (list[i-1] >= list[j]) j--;
            swap(list[i-1], list[j]);
            reverse(&list[i], &list[len]);
            break;
        }

    return list;
}

int main()
{
  string a = "23651";
  string b = next_permutation(a, a.length());

  cout << b << endl;

  return 0;
}