『壹』 關於全排列的演算法問題
最低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節講了
『貳』 關於全排列演算法實現（請幫忙注釋這些代碼）
全排列用的是
置換演算法，
演算法這東西重在理解。具體代碼並不那麼重要。
全排列是將一組數按一定順序進行排列，如果這組數有n個，那麼全排列數為n!個。現以{1,
2,
3,
4,
5}為
例說明如何編寫全排列的遞歸演算法。
1、首先看最後兩個數4,
5。
它們的全排列為4
5和5
4,
即以4開頭的5的全排列和以5開頭的4的全排列。
由於一個數的全排列就是其本身，從而得到以上結果。
2、再看後三個數3,
4,
5。它們的全排列為3
4
5、3
5
4、
4
3
5、
4
5
3、
5
3
4、
5
4
3
六組數。
即以3開頭的和4,5的全排列的組合、以4開頭的和3,5的全排列的組合和以5開頭的和3,4的全排列的組合.
從而可以推斷，設一組數p
=
{r1,
r2,
r3,
...
,rn},
全排列為perm(p)，pn
=
p
-
{rn}。
因此perm(p)
=
r1perm(p1),
r2perm(p2),
r3perm(p3),
...
,
rnperm(pn)。當n
=
1時perm(p}
=
r1。
為了更容易理解，將整組數中的所有的數分別與第一個數交換，這樣就總是在處理後n-1個數的全排列。
演算法如下：
#include
<stdio.h>
int
n
=
0;
void
swap(int
*a,
int
*b)
{
int
m;
m
=
*a;
*a
=
*b;
*b
=
m;
}
void
perm(int
list[],
int
k,
int
m)
{
int
i;
if(k
>
m)
{
for(i
=
0;
i
<=
m;
i++)
printf("%d
",
list[i]);
printf("\n");
n++;
}
else
{
for(i
=
k;
i
<=
m;
i++)
{
swap(&list[k],
&list[i]);
perm(list,
k
+
1,
m);
swap(&list[k],
&list[i]);
}
}
}
int
main()
{
int
list[]
=
{1,
2,
3,
4,
5};
perm(list,
0,
4);
printf("total:%d\n",
n);
return
0;
}
『叄』 全排列計算公式是什麼
公式：全排列數f(n)=n!(定義0!=1)。
從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m=n時所有的排列情況叫全排列。
鄰位對換法
遞減進位制數法的中介數進位不頻繁，求下一個排列在不進位的情況下很容易。
這就啟發我們，能不能設計一種演算法，下一個排列總是上一個排列某相鄰兩位對換得到的。
遞減進位制數字的換位是單向的，從右向左，而鄰位對換法的換位是雙向的。 這個演算法可描述如下：
對1—n-1的每一個偶排列，n從右到左插入n個空檔(包括兩端)，生成1—n的n個排列。
對1—n-1的每一個奇排列，n從左到右插入n個空檔，生成1—n的n個排列。
對[2,n]的每個數字都是如此。
『肆』 求高手解答本「實現數組全排列」的演算法思想的詳細思路。
如果排列因子數量很少， 可以用2進制位來表示。
如：["a", "b", "c", "d", "e"]可以按位表示
0 0 0 0 0
相應位為1時表示， 使用該因子。
『伍』 C語言 求此全排列遞歸演算法解析
used數組是全局變數有隱含初值0；
關於全排列的演算法你可以理解為深搜加回溯。
#include
#define
MAX
10
int
used[MAX];
//用來標記數字是否已經在前面使用過
int
result[MAX];
//存放結果
int
N;
void
print()
//輸出結果
{
int
i;
for(i=0;i
printf("%d
",result[i]);
printf("\n");
}
void
proc(int
step)
//step用來記錄已經擺好了幾個數
{
int
i;
if(step==N)
//如果已經擺好了N個數，那麼結果就產生了，就輸出結果
print();
else
{
for(i=0;i
{
if(!used[i])
//沒有使用過
{
used[i]=1;
//標記i已經使用
result[step]=i+1;
//記錄結果
proc(step+1);
//遞歸求解
used[i]=0;
//這里就是所謂的回溯，也許比較難理解，你可以人工走一遍加深理解。其實回溯的主要想法是"還原現場".當執行到這一步時，i+1
這個數放在第step個位置的情況已經解決了，我們就要拿出i+1這個數，把它標記為未使用。
}
}
}
}
int
main()
{
scanf("%d",&N);
proc(0);
return
0;
}
『陸』 全排列遞歸演算法
希望我的答復可以幫助你加深理解：
第一，perm函數中的條件for(int i=k;i<=m;i++)應更正為 for(int i=k;i<m;i++)
第二，你可以在核心步驟的前後列印有關變數的值，分析查看每一步的具體執行情況，這是編程調試的重要能力，要加強。
第三，以下是我提供的附件程序及運行結果（以1,2,3這個數組的全排列），可輔助分析：
1. 程序源碼=================================================
#include <stdio.h>
#include <stdlib.h>
int N,P=0;
void swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void perm(int a[],int k,int m,int pk,int pm)
{
int i;
/*k為中間變數，m初始化為參與排列元素的起始坐標和終止坐標
pk,pm分別表示參與排列元素的起始坐標和終止坐標，整個遞歸過程保持不變*/
if(k==m)
{
printf("----->perm %d :\n",P/N+1);/*列印提示*/
for(i=pk;i<pm;i++)
{
printf("%d ",a[i]);
P=P+1;
}
printf("\n\n");
}
else
{
for(i=k;i<m;i++)
{
printf("a %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("b %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
perm(a,k+1,m,pk,pm);
printf("c %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("d %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
}
}
}
int main()
{
/*調節以下N值及對應數組內容，可列印對應數組對應的全排列*/
N=3;
int t[]={1,2,3};
/*調節以上N值及對應數組內容，可列印對應數組對應的全排列*/
perm(t,0,N,0,N);
printf("----->Over!\n");/*列印提示*/
system("pause");
return 0;
}
2.列印結果 ============================================================
a 0,0,1,2,3
b 0,0,1,2,3
a 1,1,1,2,3
b 1,1,1,2,3
a 2,2,1,2,3
b 2,2,1,2,3
----->perm 1 :
1 2 3
c 2,2,1,2,3
d 2,2,1,2,3
c 1,1,1,2,3
d 1,1,1,2,3
a 2,1,1,2,3
b 2,1,1,3,2
a 2,2,1,3,2
b 2,2,1,3,2
----->perm 2 :
1 3 2
c 2,2,1,3,2
d 2,2,1,3,2
c 2,1,1,3,2
d 2,1,1,2,3
c 0,0,1,2,3
d 0,0,1,2,3
a 1,0,1,2,3
b 1,0,2,1,3
a 1,1,2,1,3
b 1,1,2,1,3
a 2,2,2,1,3
b 2,2,2,1,3
----->perm 3 :
2 1 3
c 2,2,2,1,3
d 2,2,2,1,3
c 1,1,2,1,3
d 1,1,2,1,3
a 2,1,2,1,3
b 2,1,2,3,1
a 2,2,2,3,1
b 2,2,2,3,1
----->perm 4 :
2 3 1
c 2,2,2,3,1
d 2,2,2,3,1
c 2,1,2,3,1
d 2,1,2,1,3
c 1,0,2,1,3
d 1,0,1,2,3
a 2,0,1,2,3
b 2,0,3,2,1
a 1,1,3,2,1
b 1,1,3,2,1
a 2,2,3,2,1
b 2,2,3,2,1
----->perm 5 :
3 2 1
c 2,2,3,2,1
d 2,2,3,2,1
c 1,1,3,2,1
d 1,1,3,2,1
a 2,1,3,2,1
b 2,1,3,1,2
a 2,2,3,1,2
b 2,2,3,1,2
----->perm 6 :
3 1 2
c 2,2,3,1,2
d 2,2,3,1,2
c 2,1,3,1,2
d 2,1,3,2,1
c 2,0,3,2,1
d 2,0,1,2,3
----->Over!
請按任意鍵繼續. . .
『柒』 關於全排列的生成演算法
個人一點見解，希望對你有所幫助。
依我之見，你的對換部分出了一點點問題。只要作如下修改即可：
1、exchange 改為：
procere exchange(l,r:integer);
var
t,len:integer;
begin
if l=r then exit;
len:=r-l+1;
len:=len div 2;
for i:=1 to len do
begin
t:=a[l+i-1];
a[l+i-1]:=a[r-i+1];
a[r-i+1]:=t;
end;
end;
2、主過程中exchange(p,n)改為exchange(i+1,n)。
『捌』 求遍歷全排列的演算法
全排列的生成演算法就是對於給定的字元集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。
常見的有四種全排列演算法：
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法
這里著重介紹字典序法
對給定的字元集中的字元規定了一個先後關系，在此基礎上規定兩個全排列的先後是從左到右逐個比較對應的字元的先後。
[例]字元集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。
[注意] 一個全排列可看做一個字元串，字元串可有前綴、後綴。
1）生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的後綴上。
[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最後面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個了。否則找出第一次出現下降的位置。
『玖』 遞歸全排列演算法比較 誰能幫我分析下全排列演算法的生成特點和優劣啊
生成全排列演算法有2種，一種是遞歸的，一種是非遞歸的
遞歸比較容易想一點，網上也容易搜到。非遞歸的難一點，《STL源碼剖析》這書里有很詳細的講解。
