生成全排列的算法是針對給定的字符集以有效的方式枚舉所有可能的全排列，而不會重復或遺漏。n個字符集的任意排列可以與1 ~ n的n個數的排列壹壹對應，因此以n個數的排列為例說明生成排列的方法。
n個字符的所有排列之間存在確定的線性順序關系。除了最後壹個排列之外的所有排列都有壹個後繼排列；除了第壹種安排，還有壹種前兆。每個排列的後繼可以從其變化最小的前任中獲得，生成所有排列的算法是從第壹個排列開始逐個生成所有排列的方法。
通常有以下方法來生成全排列:
字典排序法
增量十進制方法
十進制遞減法
正位交換法
遞歸類算法
1.字典排序法
在字典排序方法中，對於數字1，2，3的排列......n，通過從左到右逐壹比較相應數字的順序來確定不同排列的順序。例如，對於五位數排列12354和12345，排列12345排在前面，排列12354排在最後。根據這壹規定，在所有五個數字的排列中，第壹個是12345，最後壹個是54321。
字典順序算法如下:
設p是1 ~ n的完全置換:p = p1p2...pn = p1p2...pj-1ppj+1ppk+65438。
1）從排列的右端開始，找出比右邊的數字小的第壹個數字的序列號j（j從左端開始計算），即j = max {i | pi
2）在pj右邊的數中，找出所有大於pj的數中最小的數pk，即k = max { I | pi》；Pj}（右邊的數字從右到左遞增，因此k是所有大於Pj的數字中最高的數字）
3）交換pi、pk
4）然後Pj+1...PK-1ppk+1pn被求逆得到排列P”= P 1p 2...Pj-1ppjpn...PK+1ppk-。
例如，839647521是數字1 ~ 9的排列。從中生成下壹個排列的步驟如下:
從右到左，找到第壹個數字4 839647521，它比右邊的數字小。
在這個數字之後的數字中找出大於4的最小數字5 839647521。
用839657421交換5和4。
反轉7421 839651247。
所以839647521的下壹個排列是839651247。
2.增量十進制方法
在增量十進制方法中，需要中間數來從壹個排列中找到另壹個排列。如果排列p1p2中元素P1右側的數字數...圓周率...pn由ki表示，排列的中間數是對應的排列K1...基瓦尼斯國際(Kiwanis International)...KN-1。
例如，排列839647521的中間數是72642321，而7、2、6、...數字8，3，9右邊的數字比它小嗎？...分別在排列中。
中間數是計算排列的中間環節。給定壹個安排，需要下壹個安排。首先，確定其中介數量。對於安排的繼承者，其中介編號為原安排的中介編號加上1。需要註意的是，如果中間數的最後壹位kn-1+1=2，它將向前移動。通常，如果KI+1 =例如，如果排列839647521中的中介數為72642321，則下壹個排列中的中介數為6734221+1 = 67342300（因為1+1=2，所以向前移動。
獲得中間數後，可以根據它恢復相應的排列。
算法如下:
中間號碼k1，k2，...，kn-1表示數字N，n-1，...，2在排列中從右端開始，因此有必要按k1，k2、...，KN。並把它們壹個壹個地放在排列中:I從右邊開始放在ki+1的位置。如果已經放置了壹個數字，則不計算該位置，最後壹個空格放入1。
因此，從67342300可以得到排列849617523，它是839647521的後壹種排列。因為9放在第壹位，k1=6，9放在右數第七位，留下六個空位，然後放8，k2=7，8放在右數第八位，但9占據壹個位置，所以8應該放在右數第九位，以此類推。
3.十進制遞減法
在增量十進制方法中，中間數的最低位是每個二進制數1，這是壹個缺點。反轉升序十進制數以獲得降序十進制數。
839647521的中間數是6734221（k 1k 2...KN-1），它被反轉為1224376（KN-1...K2K1）。給定排列p，p的下壹個排列的中間數定義為p的中間數加上1。例如p=839647521，p的中介數為1224376，p的下壹排列的中介數為1224376+1 = 12224377，因此p的下壹排列為893647527。
給定中間數，可以通過類似於增量十進制方法的方法恢復排列。然而，在十進制系統中，下壹個排列可以直接從壹個排列中獲得，而無需首先計算中間數。具體算法如下:
1）如果p（I）= n且I
2）如果p（n）= n，找出壹個連續遞減的序列9，8，...，I，將其從排列的左端刪除，以相反的順序添加到排列的右端，然後與左邊的數字交換i-1。
例如，p=893647521的下壹個排列是983647521。在尋找983647521的下壹個排列時，因為9在最左邊，第二個位置是8，第三個位置不是7，所以8和9排在364752189的最右端，然後983647521的下壹個排列是36745265438+。例如，要找到987635421的下壹個排列，只需將9876從小到大排列到最右側，並將5與左側的數字3進行切換，即可得到534216789。
4.正位交換法
相鄰排列方法中的下壹個排列總是通過交換前壹個排列的某些相鄰兩位數來獲得。以四個元素的排列為例，通過將最後壹個元素4與前面的元素逐壹交換，可以產生四種新的排列:
1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3
然後，交換最後壹個排列末尾的兩個元素，然後將該行頂部的4與以下元素逐壹交換，以生成四個新排列:
4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4
然後交換最後壹個排列末尾的兩個元素，並將4從後向前移動:
3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2
這個循環不僅可以找到所有的排列。
5.元素增量法（N元法）
1），從原始排列P = P1p2開始...PN，將n-1添加到第n位。如果該位的值超過N，則將其除以N，用余數替換該位，並將其進位（第N位加上1）。
2）第n-1位、第n-2位、...以相同的方式處理，直到進位不再出現，並且在處理壹個排列後生成新的排列。
3）刪除具有相同元素的排列。
4）當第壹個元素的值》時；n結束了
以1，2，3三個數的排列為例:原排列為1 ^ 2 ^ 3，由此第三個元素為3，3+2 = 5，5 Mod 3 = 2，第二個元素為2，2+1 = 3，因此新排列為1 ^ 3 ^ 2。通過元素的增量，順序為:1 2 3、1 3 2、2 1 1、2 1 3、2 2 2、2 3 1、2 3 3、3 1 2、3265438。
下劃線排列中有重復元素。丟棄它們，剩下的就是所有的安排。
6.遞歸類算法
用遞歸簡潔地描述了全置換的生成方法，並有多種實現方法。
1）回溯法
回溯法通常是構造壹棵生成樹。以三要素為例；樹的節點有數據，可接受的值是1、2和3。如果1為0，則意味著沒有取值。
初始狀態為（0，0，0），第1個元素值可以分別選擇為1，2，3，因此展開了三個子節點。用同樣的方法找出這些節點的第二個元素的可能值，以此類推，壹旦新節點的三個數據都不為零，則找到壹個完整的排列方案。當嘗試了所有可能的方案後，問題的答案就出來了。
2）遞歸算法
如果p表示n個元素的排列，Pi表示沒有元素I的排列，並且（I）Pi表示在排列Pi之前具有前綴I的排列，則n個元素的排列可以遞歸地定義為:
如果n=1，置換P只有壹個元素I。
如果n & gt1，則置換p由置換（I）Pi（I = 1，2，...n-1）。
根據定義，很容易看出，如果已經生成了k-1個元素的排列，那麽可以通過在k-1個元素的每個排列Pi之前添加元素I來生成k個元素的排列。例如，兩個元素的排列是1 ^ 2和2 ^ 1，而對於另壹個元素，p1是2 ^ 3和3 ^ 2。在每個排列前加上1生成兩個新排列，即1 ^ 2 ^ 3和1 ^ 3 ^ 2，p2和p3為1 ^ 3和3652。可以通過相同的方法生成新的排列2 1 3、2 3 1、3 1 2和3 2 1。
3）循環移位法
如果已經生成了k-1個元素的排列，則在每個排列後添加元素k，使其成為k個元素的排列，然後每個排列循環地向左（右）移動，每次移動都會生成新的排列。
例如，兩個元素的排列是1 ^ 2和2 ^ 1。在1 ^ 2之後，添加3成為新的排列1 ^ 2 ^ 3，並將其向左循環移動以生成新的排列2 ^ 3 1、3 ^ 1 ^ 2，同樣，2 ^ 1 ^ 3、1 ^ 3 ^ 2和3 ^ 2 1可以生成新的排列。