全排列

標籤: 暫無標籤

209

更新時間: 2013-09-05

廣告

從n個不同元素中任取m(m≤n)個元素,按照一定的順序排列起來,叫做從n個不同元素中取出m個元素的一個排列。當m=n時所有的排列情況叫全排列。

全排列 -簡介

  如1,2,3三個元素的全排列為:
  1,2,3
  1,3,2
  2,1,3
  2,3,1
  3,1,2
  3,2,1
全排列 -如果用遞歸演算法結果是

  1,2,3
  1,3,2
  2,1,3
  2,3,1
  3,2,1
  3,1,2
  這是由於演算法只是考慮到了如何輸出全排列,而沒有考慮到換位是否有問題。所以我提出了解決方案,就是換位函數修改下
  如 1 2 3 換位的話 ,不應該直接 3 2 1這樣 ,讓3和1直接換位; 而是讓3排在最前後 ,1 2 依次向後
全排列 -全排列公式

  全排列數f(n)=n!(定義0!=1)
全排列 -基本演算法

廣告

  以下介紹全排列演算法四種:
  (A)字典序法
  (B)遞增進位制數法
  (C)遞減進位制數法
  (D)鄰位對換法
(A)字典序法

  對給定的字符集中的字元規定了一個先後關係,在此基礎上規定兩個全排列的先後是從左到右逐個比較對應的字元的先後。 [例]字符集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。
  [注意] 一個全排列可看做一個字元串,字元串可有前綴、後綴。
  1)生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有儘可能長的共同前綴,也即變化限制在儘可能短的後綴上。
  [例]839647521是1--9的排列。1—9的排列最前面的是123456789,最後面的是987654321,從右向左掃描若都是增的,就到了987654321,也就沒有下一個了。否則找出第一次出現下降的位置。
B 遞增進位制數法

廣告

  1)由排列求中介數 在字典序法中,中介數的各位是由排列數的位決定的.中介數位的下標與排列的位的下標一致。
  在遞增進位制數法中,中介數的各位是由排列中的數字決定的。即中介數中各位的下標與排列中的數字(2—n)一致。可看出n-1位的進位鏈。 右端位逢2進1,右起第2位逢3進1,…, 右起第i位逢i+1進1,i=1,2,…,n-1. 這樣的中介數我們稱為遞增進位制數。 上面是由中介數求排列。
  由序號(十進位數)求中介數(遞增進位制數)如下:
  m=m1,0≤m≤n!-1
  m1=2m2+kn-1,0≤kn-1≤1
  m2=3m3+kn-2,0≤kn-2≤2
  ……………
  mn-2=(n-1)mn-1+k2,0≤k2≤n-2
  mn-1=k1,0≤k1≤n-1
  p1p2…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)↑←→849617523
  6×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的位置。
C 遞減進位制數法

廣告

  在遞增進位制數法中,中介數的最低位是逢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
  [注意]求下一個排列十分容易
D 鄰位對換法

  遞減進位制數法的中介數進位不頻繁,求下一個排列在不進位的情況下很容易。這就啟發我們,能不能設計一種演算法,下一個排列總是上一個排列某相鄰兩位對換得到的。遞減進位制數字的換位是單向的,從右向左,而鄰位對換法的換位是雙向的。 這個演算法可描述如下:
  對1—n-1的每一個偶排列,n從右到左插入n個空檔(包括兩端),生成1—n的n個排列。
  對1—n-1的每一個奇排列,n從左到右插入n個空檔,生成1—n的n個排列。
  對[2,n]的每個數字都是如此。
  839647521
  字典序法 遞增進位製法 遞減進位製法 鄰位對換法
  下一個 839651247 849617523 893647521 836947521
  中介數 72642321↑ 67342221↑ 12224376↓ 10121372↓
  序 號 297191 279905 340989 203393
全排列 -下面來說說全排列問題的遞歸與非遞歸解法.

廣告

1.遞歸(分治法思想):

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

廣告

  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為止。演算法結束。
  int b[N];
  int is_train(int a[],int n)
  {
  int i,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);
  else return(1);
  }
  }
  void train(int a[],int n)
  {
  int i,j,t,temp,count=1 ;
  t=1 ;
  printf("input the %3dth way:",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 ;
  else t=1 ;
  if(t)
  {
  i=n ;
  "
  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("input the %3dth way:",count);
  for(i=1;i<=n;i++)
  printf("%3d",a[i]);
  printf("n");
  }
  }
  }
  }
全排列 -C語言實現Heap演算法全排列

廣告

  #include
  #define MAX 100
  void process(char *c,int n){
  int i = 0;
  while(i < n){
  printf("%c",c[i]);
  i++;
  }
  printf("\n");
  }
  void perm(char *list,int n){
  int k;
  char tmp;
  int i = n;
  int count[MAX];
  count[i - 1] = 1;
  while(i > 2){
  i--;
  count[i - 1] = 1;
  }
  process(list,n);
  do{
  if(count[i - 1] < i){
  if(i % 2 != 0)
  k = 1;
  else
  k = count[i - 1];
  tmp = list[k - 1];
  list[k - 1] = list[i - 1];
  list[i - 1] = tmp;
  count[i - 1] += 1;
  i = 2;
  process(list,n);
  }else{
  count[i - 1] = 1;
  i += 1;
  }
  }while(i <= n);
  }
  int main(){
  char c[] = {'a','b','c','d'};
  perm(c,4);
  }
全排列 -Java 源代碼實現

  public class Test {
  public static char[] text = { 'a', 'b', 'c', 'd', 'e' };
  public static void main(String[] args) {
  permutation(text, 0, text.length);
  System.exit(0);
  }
  /**
  * 全排列輸出
  *@param a[] 要輸出的 字元 數組
  *@param m 輸出字元數組的起始位置
  *@param n 輸出字元數組的長度
  */
  public static void permutation(char a[], int m, int n) {
  int i;
  char t;
  if (m < n - 1) {
  permutation(a, m + 1, n);
  for (i = m + 1; i < n; i++) {
  t = a[m];
  a[m] = a[i];
  a[i] = t;
  permutation(a, m + 1, n);
  t = a[m];
  a[m] = a[i];
  a[i] = t;
  }
  } else {
  printResult(a);
  }
  }
  /**
  * 輸出指定字元數組
  *@param 將要輸出的字元數組
  */
  public static void printResult(char[] text) {
  for (int i = 0; i < text.length; i++) {
  System.out.print(text[i]);
  }
  System.out.println();
  }
  }
全排列 -Pascal源代碼

  program e;
  var
  n,t:longint;
  a:array[1..8] of integer;
  flag:array[1..8] of boolean;
  procedure search(depth:integer); {depth 變數表示正在搜索第幾個元素}
  var
  i:integer;
  begin
  if(depth>n) then {depth>n表明已經搜索到了第n個數,那麼輸出結果}
  begin
  for i:=1 to n do write(a[i]:4);
  writeln;
  inc(t);
  exit; {此種結果輸出后,退出該層搜索}
  end;
  for i:=1 to n do {枚舉下一個出現的元素}
  if flag[i]=false then {判斷是否已經出現過}
  begin
  a[depth]:=i; {沒有出現,則把第depth個數設為i}
  flag[i]:=true; {給這個標誌變數給出出現的標誌}
  search(depth+1); {遞歸搜索下一個元素}
  flag[i]:=false; {回溯,此時恢復這個標誌變數為沒出現的標誌}
  end;
  end;
  begin
  writeln('input N:');
  read(n);
  t:=0;
  fillchar(flag,sizeof(flag),false); {賦初值,設定全部沒有出現過}
  search(1);
  writeln('Total=',t);
  end.
全排列 -VB源代碼

  Option Explicit
  '修改:TZWSOHO
  Private Sub Command1_Click()
  Dim nt As Double: nt = Timer
  List1.Visible = False: List1.Clear
  Permutation "", Text1.Text
  List1.Visible = True
  Debug.Print Timer - nt,
  End Sub
  ' 遞歸求全排列
  '演算法描述:
  '以8位為例,求8位數的全排列,其實是8位中任取一位
  '在後加上其餘7位的全排列
  '7 位:任取一位,其後跟剩下6位的全排列
  '……
  '這樣就有兩部分,一部分為前面的已經取出來的串,另一部分為後面即將進行的全排列的串
  '參數pre即為前面已經取出來的串
  '參數str即為將要進行排列的串
  Private Sub Permutation(pre As String, s As String)
  Dim i As Long
  '// 如果要排列的串長度為1,則返回
  If Len(s) = 1 Then List1.AddItem pre & s: Exit Sub
  '// for循環即是取出待排列的串的任一位
  For i = 1 To Len(s)
  '// 遞歸,將取出的字元併入已經取出的串
  '// 那麼剩下的串即為待排列的串
  Permutation pre & Mid$(s, i, 1), Left$(s, i - 1) & Mid$(s, i + 1)
  Next
  End Sub
  C++實現
  template < class Type>
  void Perm(Type list[],int k,int m)
  {//產生list[k:m]的所有全排列
  if(k == m)
  {//只剩一個元素
  for(int i=0;i<=m;i++)cout<
  cout<
  }
  else//還有多個元素待排列,遞歸產生排列
  for(int i=k;i<=m;i++)//循環交換第一個元素與其後的所有元素實現全 //排列
  {
  Swap(list[k],list[i]);
  Perm(list,k+1,m);
  Swap(list[k],list[i]);
  }
  }
  我有一個非遞歸演算法
  #include
  int *n;
  void arge( int *x,int size)
  {
  int *t;
  int totoal=0;
  int pos=size-2;
  int just=0;
  t=new int;
  for( int i=0 ;i
  t=1;
  while(1)
  {
  for( i=0 ; i
  printf("%d ",x);
  printf("\n");
  totoal++;
  pos=size-2;
  while(x[pos]>x[pos+1]) //
  {
  pos--;
  t[x[pos+1]-1]=0;
  }
  if(pos<0)
  break;
  t[x[pos+1]-1]=0; //複位上一個
  t[x[pos]-1]=0;
  for( i=x[pos]+1; i<=size; i++)
  {
  if(t[i-1]==0)
  {
  x[pos]=i;
  t=1;
  break;
  }
  }
  t[x[pos]-1]=1;
  for( i=pos+1; i
  {
  for( int j=1; j<=size; j++)
  {
  if(t[j-1]==0)
  {
  x=j;
  t[j-1]=1;
  break;
  }
  }
  }
  }
  printf("totoal= %d\n",totoal);
  delete [t];
  }
  int main()
  {
  int m;
  scanf("%d",&m);
  n=new int[m];
  for( int i=0 ;i
  n=i+1;
  arge(n,m);
  delete [n];
  return 0;
  }
用字典序法實現全排列(VC++實現)

  #include
  int * array;
  int num;
  inline void xchg(int &a, int &b)
  {
  int c=a;
  a=b;
  b=c;
  }
  //從pos到num的數據進行翻轉
  void invert(int pos)
  {
  int count=num-pos+1;
  for(int i=0; i
  xchg(array[pos+i],array[num-i]);
  }
  //檢查輸入中是否有重複數值
  bool is_valid(int data, int serial)
  {
  for(int i=1; i
  if(array[i]==data)
  {
  printf("全排列中不能有數據重複!\n");
  return 0;
  }
  return 1;
  }
  //輸出全排列
  void print_permutation(int m)
  {
  printf("之後第%d個全排列: ", m);
  for(int i=1; i<=num; i++)
  printf("%d ", array[i]);
  printf("\n");
  }
  // 字典序全排列的主體
  void dictionary()
  {
  printf("輸入起始的全排列:\n");
  for(int i=1; i<=num; i++)
  {
  int data;
  scanf("%d", &data);
  if(is_valid(data,i))
  array[i]=data;
  else
  return;
  }
  if(num==1)
  {
  printf("只有一個數,不需進行排列!\n");
  return;
  }
  int count;
  printf("預測之後第幾個序列:\n");
  scanf("%d", & count);
  //一次循環找下一個全排列
  for(int m=1; m<=count; m++)
  {
  int pos1=0;
  int pos2;
  //從num-1開始,找到第一個比右邊值小的位置
  for(int j=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(int n=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);
  }
  }
  void main()
  {
  printf("輸入要進行全排列的位數\n");
  scanf("%d", &num);
  array=new int[num+1];
  while(1)
  dictionary();
  }

廣告