全排列算法與全組合算法

1. 前言

本文介紹了經常使用的排列組合算法，包含全排列算法，全組合算法，m個數選n個組合算法等。

2. 排列算法

常見的排列算法有：

(A)字典序法

(B)遞增進位制數法

(C)遞減進位制數法

(D)鄰位對換法

(E)遞歸法

介紹經常使用的兩種：

(1) 字典序法

對給定的字元集中的字元規定了一個先後關系，在此基礎上依照順序依次産生每一個排列。

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

生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有字典順序中相鄰的字元串。這就要求這一個與下一個有盡可能長的共同字首，也即變化限制在盡可能短的字尾上。

算法思想：

設P是[1,n]的一個全排列。

P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|Pi<Pi+1}, k=max{i|Pi>Pj} ,對換Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻轉， P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一個

樣例:839647521的下一個排列.

從最右開始,找到第一個比右邊小的數字4(由于4<7，而7>5>2>1),再從最右開始,找到4右邊比4大的數字5(由于4>2>1而4<5),交換4、5,此時5右邊為7421,倒置為1247,即得下一個排列:839651247.用此方法寫出全排列的非遞歸算法例如以下

該方法支援資料反複，且在C++ STL中被採用。

(2) 遞歸法

設一組數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。

如：求{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的全排列的組合.

#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;
 
}      

3. 組合算法

3.1 全組合

在此介紹二進制轉化法，即，将每一個組合與一個二進制數相應起來，枚舉二進制的同一時候，枚舉每一個組合。如字元串：abcde

00000 <– –> null

00001<– –> e

00010 <– –> d

… …

11111 <– –> abcde

3.2 從n中選m個數

(1) 遞歸

a. 首先從n個數中選取編号最大的數，然後在剩下的n-1個數裡面選取m-1個數，直到從n-(m-1)個數中選取1個數為止。

b. 從n個數中選取編号次小的一個數，繼續運作1步，直到目前可選編号最大的數為m。

以下是遞歸方法的實作：

/// 求從數組a[1..n]中任選m個元素的全部組合。
 
/// a[1..n]表示候選集，n為候選集大小，n>=m>0。
 
/// b[1..M]用來存儲目前組合中的元素(這裡存儲的是元素下标)，
 
/// 常量M表示滿足條件的一個組合中元素的個數，M=m，這兩個參數僅用來輸出結果。
 
voidcombine( inta[], intn, intm,  intb[], constint M )
{
  for(inti=n; i>=m; i--)   // 注意這裡的循環範圍
  {
    b[m-1] = i - 1;
    if(m > 1)
      combine(a,i-1,m-1,b,M);
    else                    // m == 1, 輸出一個組合
    {
      for(intj=M-1; j>=0; j--)
      	cout << a[b[j]] << " ";
      cout << endl;
    }
  }
}      

(2) 01轉換法

本程式的思路是開一個數組，其下标表示1到n個數，數組元素的值為1表示其代表的數被選中，為0則沒選中。

首先初始化，将數組前n個元素置1，表示第一個組合為前n個數。

然後從左到右掃描數組元素值的“10”組合，找到第一個“10”組合後将其變為“01”組合，同一時候将其左邊的所有“1”所有移動到數組的最左端。

當第一個“1”移動到數組的n-m的位置，即n個“1”所有移動到最右端時，就得到了最後一個組合。

比如求5中選3的組合：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

1 1 1 0 0 //1,2,3 1 1 0 1 0 //1,2,4 1 0 1 1 0 //1,3,4 0 1 1 1 0 //2,3,4 1 1 0 0 1 //1,2,5 1 0 1 0 1 //1,3,5 0 1 1 0 1 //2,3,5 1 0 0 1 1 //1,4,5 0 1 0 1 1 //2,4,5 0 0 1 1 1 //3,4,5