排列生成演算法

❶ 求遍歷全排列的演算法

全排列的生成演算法就是對於給定的字元集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。

常見的有四種全排列演算法：
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法

這里著重介紹字典序法

對給定的字元集中的字元規定了一個先後關系，在此基礎上規定兩個全排列的先後是從左到右逐個比較對應的字元的先後。

[例]字元集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。

[注意] 一個全排列可看做一個字元串，字元串可有前綴、後綴。

1）生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的後綴上。

[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最後面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個了。否則找出第一次出現下降的位置。

❷ 圓排列的圓排列生成演算法

現在已經存在很多種全排列演算法，例如字典序演算法、遞增進位制演算法、遞減進位制演算法、鄰位對換法。這里介紹一下圓排列生成的演算法。我們不妨用1、2、...、n來表示n個元素
對於 ，圓排列僅有一種。
對於 ，假設我們已經得到了n-1時的圓排列，我們由此序列來生成n的圓排列。
假設 為n-1時的其中一個圓排列，那麼我們可以將n分別插入到 後，由此生成新的n-1種排列......


對 個圓排列均進行此操作，即可生成一組新的一組排列，此排列即為n時的圓排列。