全排列 - 中文百科知識

公式 全排列 全排列，是指從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列，當m=n時所有的排列的叫法。

可以採用樹的結構表示全排列生成算法。

遞減進位制數法的中介數進位不頻繁，求下一個排列在不進位的情況下很容易。

對於生成樹中的第層，每一個節點中介數的前-2位繼承於其父節點的中介數，中介數最後一位為該層新加入的數減去其右邊相鄰的數。

由於所有全排列算法必須至少支持中介數映射或遞推操作中的一種，因而上面的加速框架可以適應所有的全排列生成算法，為其提供並行加速功能。

基本信息中文名：全排列英文名：fullarray拼音：quanpailie公式全排列數f(n)=n!(定義0!=1)遞歸算法1,2,31,3,22,1,32,3,13,2,13,1,2這是由於算法只是考慮到了如何輸出全排列，而沒有考慮到換位是否有問題。

所以我提出了解決方案，就是換位函式修改下如123換位的話,不應該直接321這樣,讓3和1直接換位;而是讓3排在最前後,12依次向後基本算法以下介紹全排列算法四種：(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-1位的進位鏈。

右端位逢2進1，右起第2位逢3進1，…，右起第i位逢i+1進1，i=1,2,…,n-1.這樣的中介數我們稱為遞增進位制數。

上面是由中介數求排列。

由序號（十進制數）求中介數（遞增進位制數）如下：m=m1,0≤m≤n!-1m1=2m2+kn-1,0≤kn-1≤1m2=3m3+kn-2,0≤kn-2≤2……………mn-2=(n-1)mn-1+k2,0≤k2≤n-2mn-1=k1,0≤k1≤n-1p1p2…pn←→(k1k2…kn-1)↑←→m在字典序法中由中介數求排列比較麻煩，我們可以通過另外定義遞增進位制數加以改進。

為方便起見，令ai+1=kn-1，i=1,2,…,n-1(k1k2…kn-1)↑=(anan-1…a2)↑ai：i的右邊比i小的數字的個數在這樣的定義下，有839647521←→(67342221)↑(67342221)↑+1=(67342300)↑←→8496175236×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1=279905由(anan-1…a2)↑求p1p2…pn。

從大到小求出n,n-1,…,2,1的位置_..._n__…_(an個空格)n的右邊有an個空格。

n-1的右邊有an-1個空格。

…………2的右邊有a2個空格。

最後一個空格就是1的位置。

遞減進位制數在遞增進位制數法中，中介數的最低位是逢2進1，進位頻繁，這是一個缺點。

把遞增進位制數翻轉,就得到遞減進位制數。

(anan-1…a2)↑→(a2a3…an-1an)↓839647521→(12224376)↓(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989[注意]求下一個排列十分容易鄰位對換法遞減進位制數法的中介數進位不頻繁，求下一個排列在不進位的情況下很容易。

這就啟發我們，能不能設計一種算法，下一個排列總是上一個排列某相鄰兩位對換得到的。

遞減進位制數字的換位是單向的，從右向左，而鄰位對換法的換位是雙向的。

這個算法可描述如下：對1—n-1的每一個偶排列，n從右到左插入n個空檔(包括兩端)，生成1—n的n個排列。

對1—n-1的每一個奇排列，n從左到右插入n個空檔，生成1—n的n個排列。

對[2,n]的每個數字都是如此。

839647521字典序法遞增進位製法遞減進位製法鄰位對換法下一個839651247849617523893647521836947521中介數72642321↑67342221↑12224376↓10121372↓序號297191279905340989203393生成樹生成樹中介數可以採用樹的結構表示全排列生成算法，以數字的全排列生成算法為例，從最小的數1開始，其全排列只有一種可能；加入數字2，數字2可以插入在1的後邊或前邊，有兩個不同位置；再加入3，對於第二層中的每一種不同排列，都可以通過將3插入不同位置得到三種不同的排列數，共有6種排列數；一次類推可以得到個數的全排列。

基於此，可以構造一種新的中介數，其定義如下：全排列生成樹與生成樹中介數示意圖對於生成樹中的第層，每一個節點中介數的前-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.對於任意的生成樹中介數，都通過類似的過程計算對應的排列數。

不難看出，從生成樹中介數還原排列數的時間複雜度也是。

遞歸與非遞歸遞歸(分治法思想)設(ri)perm(X)表示每一個全排列前加上前綴ri得到的排列.當n=1時,perm(R)=(r)其中r是唯一的元素,這個就是出口條件.當n>1時,perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)構成.voidPerm(list[],intk,intm)//k表示前綴的位置,m是要排列的數目.{if(k==m-1)//前綴是最後一個位置,此時列印排列數.{for(inti=0;i{printf("%d",list[i]);}printf("\n");}else{for(inti=k;i{//交換前綴,使之產生下一個前綴.Swap(list[k],list[i]);Perm(list,k+1,m);//將前綴換回來,繼續做上一個的前綴排列.Swap(list[k],list[i]);}}}//此處為引用,交換函式.函式調用多,故定義為內聯函式.inlinevoidSwap(int&a,int&b){inttemp=a;a=b;b=temp;}函式Perm(intlist[],intk,intm)是求將list的第0~k-1個元素作為前綴、第k~m個元素進行全排列得到的全排列，如果k為0，且m為n，就可以求得一個數組中所有元素的全排列。

其想法是將第k個元素與後面的每個元素進行交換，求出其全排列。

這種算法比較節省空間。

非遞歸n個數的排列可以從1.2....n開始,至n.n-1....2.1結束。

也就是按數值大小遞增的順序找出每一個排列。

以6個數的排列為例，其初始排列為123456,最後一個排列是654321,如果當前排列是124653,找它的下一個排列的方法是，從這個序列中從右至左找第一個左鄰小於右鄰的數，如果找不到，則所有排列求解完成，如果找得到則說明排列未完成。

本例中將找到46,計4所在的位置為i,找到後不能直接將46位置互換，而又要從右到左到第一個比4大的數，本例找到的數是5，其位置計為j，將i與j所在元素交換125643,然後將i+1至最後一個元素從小到大排序得到125346，這就是124653的下一個排列，如此下去，直至654321為止。

算法結束。

intb[N];intis_train(inta[],intn){inti,j,k=1;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++)if(a[j]/*判斷是否降序*/if(k>1)is_train(b,k);elsereturn(1);}}voidtrain(inta[],intn){inti,j,t,temp,count=1;t=1;printf("inputthe%3dthway:",count);for(i=1;i<=n;i++)printf("%3d",a[i]);printf("\n");while(t){i=n;j=i-1;/*從右往左找,找第一個左鄰比右鄰小的位置*/while(j&&a[j]>a[i]){j--;i--;}if(j==0)t=0;elset=1;if(t){i=n;/*從右往左找,找第一個比front大的位置*/while(a[j]>a[i])i--;temp=a[j],a[j]=a[i],a[i]=temp;quicksort(a,j+1,N);/*調用快速排序*//*判斷是否符合調度要求*/if(is_train(a,N)==1){count++;printf("inputthe%3dthway:",count);for(i=1;i<=n;i++)printf("%3d",a[i]);printf("n");}}}}Pascalprograme;varn,t:longint;a:array[1..8]ofinteger;flag:array[1..8]ofboolean;proceduresearch(depth:integer);{depth變數表示正在搜尋第幾個元素}vari:integer;beginif(depth>n)then{depth>n表明已經搜尋到了第n個數，那么輸出結果}beginfori:=1tondowrite(a[i]:4);writeln;inc(t);exit;{此種結果輸出後，退出該層搜尋}end;fori:=1tondo{枚舉下一個出現的元素}ifflag[i]=falsethen{判斷是否已經出現過}begina[depth]:=i;{沒有出現，則把第depth個數設為i}flag[i]:=true;{給這個標誌變數給出出現的標誌}search(depth+1);{遞歸搜尋下一個元素}flag[i]:=false;{回溯，此時恢復這個標誌變數為沒出現的標誌}end;end;beginwriteln('inputN:');read(n);t:=0;fillchar(flag,sizeof(flag),false);{賦初值，設定全部沒有出現過}search(1);writeln('Total=",t);end.VBOptionExplicit"修改:TZWSOHOPrivateSubCommand1_Click()DimntAsDouble:nt=TimerList1.Visible=False:List1.ClearPermutation"",Text1.TextList1.Visible=TrueDebug.PrintTimer-nt,EndSub'遞歸求全排列'算法描述:'以8位為例，求8位數的全排列，其實是8位中任取一位'在後加上其餘7位的全排列'7位：任取一位，其後跟剩下6位的全排列'……'這樣就有兩部分，一部分為前面的已經取出來的串，另一部分為後面即將進行的全排列的串'參數pre即為前面已經取出來的串'參數str即為將要進行排列的串PrivateSubPermutation(preAsString,sAsString)DimiAsLong'//如果要排列的串長度為1，則返回IfLen(s)=1ThenList1.AddItempre&s:ExitSub'//for循環即是取出待排列的串的任一位Fori=1ToLen(s)'//遞歸，將取出的字元併入已經取出的串'//那么剩下的串即為待排列的串Permutationpre&Mid$(s,i,1),Left$(s,i-1)&Mid$(s,i+1)NextEndSub字典序法#includeint*array;intnum;inlinevoidxchg(int&a,int&b){intc=a;a=b;b=c;}//從pos到num的數據進行翻轉voidinvert(intpos){intcount=num-pos+1;for(inti=0;ixchg(array[pos+i],array[num-i]);}//檢查輸入中是否有重複數值boolis_valid(intdata,intserial){for(inti=1;iif(array[i]==data){printf("全排列中不能有數據重複！\n");return0;}return1;}//輸出全排列voidprint_permutation(intm){printf("之後第%d個全排列:",m);for(inti=1;i<=num;i++)printf("%d",array[i]);printf("\n");}//字典序全排列的主體voiddictionary(){printf("輸入起始的全排列:\n");for(inti=1;i<=num;i++){intdata;scanf("%d",&data);if(is_valid(data,i))array[i]=data;elsereturn;}if(num==1){printf("只有一個數，不需進行排列！\n");return;}intcount;printf("預測之後第幾個序列：\n");scanf("%d",&count);//一次循環找下一個全排列for(intm=1;m<=count;m++){intpos1=0;intpos2;//從num-1開始，找到第一個比右邊值小的位置for(intj=num-1;j>0;j--)if(array[j]{pos1=j;break;}if(pos1<1||pos1>num){printf("目前全排列已為%d位數的最後一個全排列！\n\n",num);return;}//從num開始找array[pos1]小的第一個數的位置for(intn=num;n>pos1;n--)if(array[n]>array[pos1]){pos2=n;break;}xchg(array[pos1],array[pos2]);//從pos1+1到num的數進行翻轉invert(pos1+1);print_permutation(m);}}voidmain(){printf("輸入要進行全排列的位數\n");scanf("%d",#);array=newint[num+1];while(1)dictionary();}並行加速由於全排列生成中包含大量規則一致的映射和運算操作，因而可以利用並行計算的方法對全排列的生成算法進行加速，這裡提出了一種基於GPU並行計算的加速框架，可以與現有全排列生成算法整合，以實現全排列生成的加速。

具體而言，針對全排列算法本身支持的不同操作，有如下三種情況：中介數映射若全排列生成算法只支持中介數→排列的映射，那么我們可以提出如下的加速框架：考慮全排列算法A，其支持的操作為：先按照一定規則R產生中介數I，接著基於某種映射算法根據每箇中介數I計算出其對應的全排列P。

這樣，在遍歷了所有n!箇中介數後，便可以產生所有的全排列。

可以看出，其並行部分主要體現在從中介數I映射產生排列P的過程上，因而，可以採用如下的算法框架：1、產生包含所有中介數的集合S2、將S分割成為m個子集，其中m為GPU核數。

3、對於並行計算的每個核，其獨立計算每個子集Si中所有中介數→排列的映射。

4、合併所有核的計算結果。

可以看出，在理想的情況下，該算法框架的加速比應為m。

隨機遞推一般而言，生成所有全排列時，遞推算法的效率要高於中介數→排列的映射。

因而，對於支持遞推操作的全排列生成算法，可以提出更最佳化的框架。

另一方面我們可以看到，某些全排列生成算法只支持遞推操作而不存在對應的中介數，所以，對於這類算法，我們的加速框架應如下修改：考慮全排列算法A，其支持的操作為：先產生原始排列P0，接著基於某種遞推算法，根據當前得到的排列產生下一個排列，計算序列為P0→P1→P2……→Pn。

這樣，在遍歷了所有n!個排列後，便可以產生所有的全排列。

可以看出，每個單獨的遞推過程是互不干擾的。

因而，我們可以通過產生多個遞推的種子，通過多核同時遞推的方式來對遞推進行加速。

但是，由於我們對算法的細節並沒有更多的認識，所以初始種子的產生並沒有可以依賴的規則。

在實踐中，可以採用隨機的方法，隨機產生m個種子。

其對應的算法框架如下：1、隨機產生m個初始排列，其中m為GPU核數。

2、對於並行計算的每個核，其獨立根據初始排列中的一個進行遞推，直到其抵達了某個已經產生過的排列為止。

3、合併所有核的計算結果。

這裡需要注意的是，在該算法框架下，每個核的任務量很可能是不平均的。

每次遞推產生一個新排列，都需要檢查是否已經出現過。

若沒有出現過，則可以繼續遞推，否則意味著這個核的任務結束。

在實踐中，可以通過一個長度為n!的bool數組來記錄每個排列的出現情況，通過hash算法來實現O(1)時間的查找。

實踐證明，其效果是穩定、有效的。

並行遞推對於同時支持中介數和遞推方法的全排列生成算法，我們可以同時利用中介數的有序性和遞推算法的高效性，從而設計出更加高效的加速框架。

具體而言，我們可以改進隨機遞推方法，通過中介數的引用來使得各個核的任務量平均分配，從而實現全局效率的最最佳化。

考慮全排列算法A，其支持兩種操作：1、基於某個已有的排列P1，遞推出其下一個排列P2。

2、基於某箇中介數I，通過映射產生出其對應的排列P。

這樣，在進行了足夠的映射和遞推操作後，便可以產生所有的全排列。

與隨機遞推方法類似，可以看出，每個單獨的遞推過程是互不干擾的。

不同之處在於，中介數的引入使得全排列的集合S成為一個全序集，從而我們可以迅速得到某個位置的排列。

因而，我們可以通過計算和中介數映射使得每個遞推的種子均勻分布在集合中，保證每個核的工作量相同，從而避免多核中的木桶短板效應，實現效率的全局最最佳化。

具體而言，其對應的算法框架如下：1、對每個核，計算出其對應種子中介數的編號1，n!/m,2*n!/m,……這些編號均勻分布在1——n!上。

2、根據這些編號分別產生出每個核對應種子的中介數。

3、對於每個核，根據其中介數得到其遞推的種子排列。

4、每個核同時進行遞推操作，直到遞推了n!/m次為止。

5、合併所有核的計算結果。

可以看到，相比於隨機遞推方法，中介數的引入帶來了很大的優勢。

首先，全排列與中介數的一一映射關係使得全排列集合成為全序集，從而可以保證每個核的運算量是相等的，避免了並行計算中任務分配不均勻帶來的短板效應。

另一方面，每個核的任務均勻意味著可以提前知道每個核需要進行的遞推次數，從而避免了每一次遞推後都需要查看是否已經出現過的時間開銷，大大提升了效率。

實踐證明，並行遞推的算法加速比是最高的。

完備性由於所有全排列算法必須至少支持中介數映射或遞推操作中的一種，因而上面的加速框架可以適應所有的全排列生成算法，為其提供並行加速功能。

相關詞條 全錯位排列 全錯位排列被著名數學家歐拉(LeonhardEuler，1707－1783)稱為“組合數論的一個妙題”的“裝錯信封問題”的兩個特例。

套用 排列3 排列3是體育彩票管理中心下屬的彩票。

排列三”原為“7星彩”附加玩法，自2004年12月8日起從原有的七星彩玩法中分離出來，單獨使用搖獎機、搖獎球進行搖獎... 總則   獎級設定   中獎辦法    附則   兌獎規則 排列數 排列數，從n個不同元素中取出m（m≦n）個元素的所有排列的個數，叫做從n個不同元素中取出m個元素的排列數。

簡介   黃金排列數 排列3走勢圖 體育彩票排列3往期歷史獎號分布走勢圖，可以直觀地查看排三各位獎號的走勢和分布情況以及奇偶大小形態的變化走勢。

可以選擇任意時間段進行查詢，在走勢圖的選號區... 概況   選號方式   看法點評   奇偶走勢   看圖技巧 排列5 “排列5”體彩的一種，從00000-99999的數字中選取1個5位數為投注號碼進行投注“排列5”設1個獎級，為固定獎。

所選號碼與中獎號碼全部相同且順序一... 總則   相關術語   遊戲方法   玩法技巧   設獎 基因排列 基因排列genecombination基因組是指細胞或生物體的全套...環狀DNA。

5基因按照功能分類和表達先後順序線性排列如噬菌體，其基因組為...，通過粘性末端形成環狀雙鏈。

其基因的排列位置，有兩個特點：按功能分類成族排列... 原核生物中基因組合的特點   真核生物基因組織特徵 排列恆等式 "排列數A(k 康托排列 ;=a<i,i=1,2,..,n它構成一個全排列到一個整數...,...,n的排列如{1,2,3}按從小到大排列一共6個...進制數與一個排列對應起來。

他們間的對應關係可由康托展開來找到。

如我... 相關搜尋回調函式冒泡算法混料CopyMemorymallocOCI文檔Offsetpascal語言教程part-2VB變數RIP開源軟體全排列可計算性理論路由器基礎知識boostBOOST異或SPLITRegOpenKeyExdelphiPascal語言教程part-1熱門詞條HTCDESIREiPodclassicMATLABRHYTHMsailing夢醒時分富貴開心鬼德明手機即時通控訴文化局旗幟明朝歷史李旦板橋車站椒房殿烏蘭託婭皇帝殿簡志霖興華高中豹紋蛋糕超級演說家第三季郎平高雄展覽館HeraIDT人身保險仁寺洞倉鼠吳育仁婦幼醫院子虛賦復古風我的夢撒旦之子植物燈永康街清平調漂洋過海來看你聖誕帽走火馬加爵鯊魚齋藤歸蝶呂一微媞時尚診所施一公愛情喜劇現在才知道英語新聞通風設備韓安冉全排列@百科知識中文網