了解C++的童鞋都知道algorithm里面有個next_permutation可以求下一個排列數，通過《STL 源碼剖析》（或者自己讀代碼）可以知道其實現，比如：

abcd  next_permutation ->  abdc

那么，為什么abcd的下一個是abdc而不是acbd呢？

說簡單一點，用 1，2，3，4 代替 a，b，c，d，可以得到：

原排列                  中間轉換                值
1，2，3，4        3，2，1            ((3 * (3) + 2) * (2) + 1) * (1) = 23
1，2，4，3        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，所以第一位是 3
                              3 后面有(4, 2), 但只有4大于3，所以第二位是 1
                              4 后面有(2), 沒有比4 大的，所以第三位是 0
                              最后一位后面肯定沒有更大的，所以省略了一個0。

經過這種轉換以后，就得到了一種表示方式（中間轉換），這種表達方式和原排列一一對應，可以相互轉化。

仔細觀察這種中間表達方式，發現它的第一位只能是（0，1，2，3），第二位只能是（0，1，2），第三位只能是（0，1）。通常，數字是用十進制表示的，計算機中用二進制，但是現在，我用一種特殊的進制來表示數：

第一位用1進制，第二位用2進制。。。

于是就得到了這種中間表示方式的十進制值。如：

                                                              階                  
                                            |                  |                    |
1，1，0    ---->   ((1 * (3) + 1) * (2) + 0) * (1) = 8

3，1，0    ---->   ((3 * (3) + 1) * (2) + 0) * (1) = 20

這樣，就可以得到一個十進制數和一個排列之間的一一對應的關系。
現在排列數和有序的十進制數有了一一對應的關系（通過改變對應關系，可以使十進制數升序）。

到這里已經可以很容易的得到任意一個排列了，但是還沒有完，這種不定進制還有其他用處：

在寫程序的時候，很容易遇到一種情況就是：有好幾種類別的狀態需要存儲，但是對象的數量過大，需要對這種狀態表示方式進行壓縮。比如：

enum A{
A_1,
A_2,
A_3,
};

enum B{
B_1,
B_2,
B_3,
B_4,
B_5,
};

struct State{
A a : 2;
B b : 3;
};

其實 a 可以表示4個狀態，b可以表示8個狀態，因為State總共有3×5=15，也就是說4位就足夠了，這里多用了1位(當然有人可能會說，現在內存這么大，誰在乎1bit呀，告訴你，我在乎!)，不考慮對齊。

下面用上面介紹的方法來壓縮：
A 有3種狀態，B有5種狀態，那么如果把A放在高位，那么對于一個狀態(注意enum從0開始)：
(A_3，B_3),就是2×5+3=13
(A_2，B_5),就是1×5+4=9

(A_1，B_1),就是0×5+0=0
(A_3，B_5),就是2×5+4=14

這樣就可以節省1bit啦。如果這個State有1M個，那就可以節省1M內存如果有1G呢，就省1G啦，有些時候，這種表示狀態的小對象，充斥在程序的各個角落。

從數字到狀態也很容易，就像進制轉換一樣先除，再模，就OK了。

總結下：

    先說了next_permutation的問題，引出排列的另一種表達方式，然后引入了一種不定進制的表示將其轉化為十進制數字，從而使的排列數和有序的十進制數一一對應起來。
    從這種不定進制的表示方式，描述一種壓縮狀態的方法。