全排列演算法重復

⑴ 全排列的生成樹

可以採用樹的結構表示全排列生成演算法，以數字的全排列生成演算法為例，從最小的數1開始，其全排列只有一種可能；加入數字2，數字2可以插入在1的後邊或前邊，有兩個不同位置；
再加入3，對於第二層中的每一種不同排列，都可以通過將3插入不同位置得到三種不同的排列數，共有6種排列數；一次類推可以得到 個數的全排列。
基於此，可以構造一種新的中介數，其定義如下：
對於生成樹中的第n層，每一個節點中介數的前n-2位繼承於其父節點的中介數，中介數最後一位為該層新加入的數 減去其右邊相鄰的數。
如果新加入的數在最右邊，則中介數最後一位為0。
如圖所示，排列數12的中介數為0，對於生成樹第三層由節點12擴展得到的新節點，當新加入的數3位於最右邊時（即排列數123），對應的中介數為00；若3插入12中間，則中介數末位為3-2=1，即中介數為01；類似地排列數312對應的中介數為02。
不難看出，生成樹中介數也是遞減進位制數，但和遞減進位制數法是不同的。如排列數231對應的生成樹中介數為12，而遞減進位制數法對應的中介數為11。 不難看出，全排列生成樹每一層的不同節點對應的中介數都是不同的，這是因為：
（1）每個子節點中介數的前綴都從其父節點繼承得到，因此不同父節點生成的子節點中介數一定不同；
（2）同一個父節點生成的子節點，父節點的排列數每一位都是不同的，因此新加入的數插入不同位置得到的中介數的最後一位一定是不同的。
由以上兩點及歸納法即可證明生成樹每一層不同節點對應的中介數都是唯一不重復的。又全排列生成樹每一個節點的排列數是無重復無遺漏的，因此從中介數到排列數的映射是一一對應的，從而基於生成樹中介數的全排列生成演算法是完備的。 由生成樹中介數還原排列數的過程實際上就是全排列生成樹的構建過程。以生成樹中介數121為例：
（1）中介數第一位是1，說明2在1的左邊，得到21；
（2）中介數第二位為2，只能由3-1得到，說明3在1的左鄰，得到231；
（3）中介數第三位為1，只能由4-3得到，說明4在3的左鄰，得到2431.
對於任意的生成樹中介數，都通過類似的過程計算對應的排列數。不難看出，從生成樹中介數還原排列數的時間復雜度也是 。

⑵ 關於全排列的演算法問題

最低0.27元/天開通網路文庫會員，可在文庫查看完整內容>
原發布者:ON9V4Xr2gU9J7
全排列以及相關演算法在程序設計過程中，我們往往要對一個序列進行全排列或者對每一個排列進行分析。全排列演算法便是用於產生全排列或者逐個構造全排列的方法。當然，全排列演算法不僅僅止於全排列，對於普通的排列，或者組合的問題，也可以解決。本文主要通過對全排列以及相關演算法的介紹和講解、分析，讓讀者更好地了解這一方面的知識，主要涉及到的語言是C和C++。本文的節數：1.全排列的定義和公式：2.時間復雜度：3.列出全排列的初始思想：4.從第m個元素到第n個元素的全排列的演算法：5.全排列演算法：6.全排列的字典序：7.求下一個字典序排列演算法：8.C++STL庫中的next_permutation()函數：（#include）9.字典序的中介數，由中介數求序號：10.由中介數求排列：11.遞增進位制數法：12.遞減進位制數法：13.鄰位對換法：14.鄰位對換法全排列：15.鄰位對換法的下一個排列：16.鄰位對換法的中介數：17.組合數的字典序與生成：由於本文的，內容比較多，所以希望讀者根據自己的要求閱讀，不要一次性讀完，有些章節可以分開讀。第1節到第5節提供了全排列的概念和一個初始的演算法。第6節到第8節主要講述了字典序的全排列演算法。第9到第10節講了有關字典序中中介數的概念。第11到第12節主要介紹了不同的中介數方法，僅供擴展用。第13節到15節介紹了鄰位對換法的全排的有關知識。16節講了有關鄰位對換法的中介數，僅供參考。第17節講了

⑶ 10的全排列怎麼表示

10的全排列表示為10！。全排列，是指從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列，當m=n時所有的排列的叫法。可以採用樹的結構表示全排列生成演算法。遞減進位制數法的中介數進位不頻繁，求下一個排列在不進位的情況下很容易。公式為全排列數f(n)=n(定義0=1）。