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

abcd  next_permutation ->  abdc

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

說(shuō)簡(jiǎn)單一點(diǎn)，用 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)換指的是：每一個(gè)數(shù)字后面比當(dāng)前位數(shù)字大的數(shù)字的個(gè)數(shù)。比如：

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

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

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

第一位用1進(jìn)制，第二位用2進(jìn)制。。。

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

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

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

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

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

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

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;
};

其實(shí) a 可以表示4個(gè)狀態(tài)，b可以表示8個(gè)狀態(tài)，因?yàn)镾tate總共有3×5=15，也就是說(shuō)4位就足夠了，這里多用了1位(當(dāng)然有人可能會(huì)說(shuō)，現(xiàn)在內(nèi)存這么大，誰(shuí)在乎1bit呀，告訴你，我在乎!)，不考慮對(duì)齊。

下面用上面介紹的方法來(lái)壓縮：
A 有3種狀態(tài)，B有5種狀態(tài)，那么如果把A放在高位，那么對(duì)于一個(gè)狀態(tài)(注意enum從0開(kāi)始)：
(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啦。如果這個(gè)State有1M個(gè)，那就可以節(jié)省1M內(nèi)存如果有1G呢，就省1G啦，有些時(shí)候，這種表示狀態(tài)的小對(duì)象，充斥在程序的各個(gè)角落。

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

總結(jié)下：

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