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

abcd  next_permutation ->  abdc

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

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

原排列                  中間轉(zhuǎn)換                值
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
                               |      |      |                       |                    |                   |
                               |      |                              |                    |
                               |                                     |

 上面的中間轉(zhuǎn)換指的是：每一個數(shù)字后面比當(dāng)前位數(shù)字大的數(shù)字的個數(shù)。比如：

1，3，4，2  中，1 后面有(3, 4, 2) 他們都大于1，所以第一位是 3
                              3 后面有(4, 2), 但只有4大于3，所以第二位是 1
                              4 后面有(2), 沒有比4 大的，所以第三位是 0
                              最后一位后面肯定沒有更大的，所以省略了一個0。

經(jīng)過這種轉(zhuǎn)換以后，就得到了一種表示方式（中間轉(zhuǎn)換），這種表達方式和原排列一一對應(yīng)，可以相互轉(zhuǎn)化。

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

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

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

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

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

這樣，就可以得到一個十進制數(shù)和一個排列之間的一一對應(yīng)的關(guān)系。
現(xiàn)在排列數(shù)和有序的十進制數(shù)有了一一對應(yīng)的關(guān)系（通過改變對應(yīng)關(guān)系，可以使十進制數(shù)升序）。

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

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

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個狀態(tài)，b可以表示8個狀態(tài)，因為State總共有3×5=15，也就是說4位就足夠了，這里多用了1位(當(dāng)然有人可能會說，現(xiàn)在內(nèi)存這么大，誰在乎1bit呀，告訴你，我在乎!)，不考慮對齊。

下面用上面介紹的方法來壓縮：
A 有3種狀態(tài)，B有5種狀態(tài)，那么如果把A放在高位，那么對于一個狀態(tài)(注意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

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

從數(shù)字到狀態(tài)也很容易，就像進制轉(zhuǎn)換一樣先除，再模，就OK了。

總結(jié)下：

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