再議“生成全排列算法”

　　以例子說明，用0、1、2、3，四個數組成全排列。

　　首先可以知道，這四個數組成的全排列一共有4！=24個。那麼給這24個全排列編号，分别為0、1、2……23。再給定一個算法，通過編号計算出一個全排列。本文的目的就是找到這樣的算法。

　　把所有的全排列列舉出來可以發現，0在末位的有6個，1在末位的有6個，等等。

　　觀察0在末位的六個，分别是

　　1、2、3、0

　　1、3、2、0

　　2、1、3、0

　　2、3、1、0

　　3、1、2、0

　　3、2、1、0

　　可以看出這6個全排列，除了末位是0外，前面三個數正好是1、2、3的全排列

　　再觀察1在末位的六個，分别是

　　0、2、3、1

　　0、3、2、1

　　2、0、3、1

　　2、3、0、1

　　3、0、2、1

　　3、2、0、1

　　也可以看出這6個全排列，除了末位是1外，前面三個數正好是0、2、3的全排列

　　類似的，末位是2和3的6個全排列，除了末位是一樣的以外，前面三個數正好是剩下的三個數的全排列。

　　

　　于是該問題就可以用下面的步驟來解決。

　　1、根據編号确定末位數字

　　2、确定末位數字後，獲得剩餘的數字

　　3、對編号适當的處理，得到新的編号

　　4、問題演化成除了末位數字後，用新的編号和剩餘的數字，計算剩餘數字的全排列。

　　再用一個具體的例子來說明。比方說，用編号13來計算0、1、2、3的一個全排列。

　　1、先給這4個數字排好序。是0、1、2、3

　　2、計算[13/3!]+1=3，表示末位數是第3個數。注：[X]表示取X的整數部分。

　　3、把第3個數和第4個數（未排的最後1個數）交換。此時，數字的順序是0、1、3、2。藍色的表示已經排好。

　　4、新的編号為13 mod 3!=1

　　5、計算[1/2!]+1=1，表示末位數是第1個數。

　　6、把第1個數和第3個數（未排的最後1個數）交換。此時，數字的順序是3、1、0、2。藍色的表示已經排好。

　　7、新的編号為1 mod 2!=1

　　8、計算[1/1!]+1=2，表示末位數是第2個數。

　　9、把第2個數和第2個數（未排的最後1個數）交換。此時，數字的順序是3、1、0、2。藍色的表示已經排好。

　　10、因為隻剩下一個數，是以編号13對應的全排列就是3、1、0、2

　　其他的編号計算方法和此一樣。

　　後面的這個表格就是按照上面的算法得到所有的編号和全排列的關系

A(0)

A(1)

A(2)

A(3)

編号

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

　　通過這樣的算法，通過指定的編号就能算出一個全排列。

　　如果要周遊所有的全排列，則隻要周遊編号就能完成。

　　如果要随機獲得一個全排列，則随機生成一個編号，再計算出全排列就可以了。