算法之排列算法與組合算法詳解

更新時間：2014年08月28日 10:36:43 投稿：junjie

這篇文章主要介紹了算法之排列算法與組合算法詳解,本文以字典序法、遞歸法為例講解了排列算法、全組合算法等,需要的朋友可以參考下

1. 前言

本文介紹了常用的排列組合算法，包括全排列算法，全組合算法，m個數(shù)選n個組合算法等。

2. 排列算法

常見的排列算法有：
(A)字典序法
(B)遞增進(jìn)位制數(shù)法
(C)遞減進(jìn)位制數(shù)法
(D)鄰位對換法
(E)遞歸法

介紹常用的兩種：

(1) 字典序法

對給定的字符集中的字符規(guī)定了一個先后關(guān)系，在此基礎(chǔ)上按照順序依次產(chǎn)生每個排列。

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

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

算法思想：

設(shè)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翻轉(zhuǎn)， P'= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一個

例子:839647521的下一個排列.

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

該方法支持?jǐn)?shù)據(jù)重復(fù)，且在C++ STL中被采用。

(2) 遞歸法

設(shè)一組數(shù)p = {r1, r2, r3, … ,rn}, 全排列為perm(p)，pn = p – {rn}。則perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。當(dāng)n = 1時perm(p} = r1。

如：求{1, 2, 3, 4, 5}的全排列

1、首先看最后兩個數(shù)4, 5。它們的全排列為4 5和5 4, 即以4開頭的5的全排列和以5開頭的4的全排列。

由于一個數(shù)的全排列就是其本身，從而得到以上結(jié)果。

2、再看后三個數(shù)3, 4, 5。它們的全排列為3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六組數(shù)。

即以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 全組合

在此介紹二進(jìn)制轉(zhuǎn)化法，即，將每個組合與一個二進(jìn)制數(shù)對應(yīng)起來，枚舉二進(jìn)制的同時，枚舉每個組合。如字符串：abcde

00000 <– –> null
00001<– –> e
00010 <– –> d
… …
11111 <– –> abcde

3.2 從n中選m個數(shù)

(1) 遞歸

a. 首先從n個數(shù)中選取編號最大的數(shù)，然后在剩下的n-1個數(shù)里面選取m-1個數(shù)，直到從n-(m-1)個數(shù)中選取1個數(shù)為止。

b. 從n個數(shù)中選取編號次小的一個數(shù)，繼續(xù)執(zhí)行1步，直到當(dāng)前可選編號最大的數(shù)為m。

下面是遞歸方法的實現(xiàn)：

/// 求從數(shù)組a[1..n]中任選m個元素的所有組合。
 
/// a[1..n]表示候選集，n為候選集大小，n>=m>0。
 
/// b[1..M]用來存儲當(dāng)前組合中的元素(這里存儲的是元素下標(biāo))，
 
/// 常量M表示滿足條件的一個組合中元素的個數(shù)，M=m，這兩個參數(shù)僅用來輸出結(jié)果。
 
void combine( int a[], int n, int m, int b[], const int M )
 
{
 
 for(int i=n; i>=m; i--)  // 注意這里的循環(huán)范圍
 
 {
 
  b[m-1] = i - 1;
 
  if (m > 1)
 
   combine(a,i-1,m-1,b,M);
 
  else           // m == 1, 輸出一個組合
 
  {
 
   for(int j=M-1; j>=0; j--)
 
   cout << a[b[j]] << " ";
 
   cout << endl;
 
  }
 
 }
 
}

(2) 01轉(zhuǎn)換法

本程序的思路是開一個數(shù)組，其下標(biāo)表示1到n個數(shù)，數(shù)組元素的值為1表示其代表的數(shù)被選中，為0則沒選中。

首先初始化，將數(shù)組前n個元素置1，表示第一個組合為前n個數(shù)。

然后從左到右掃描數(shù)組元素值的“10”組合，找到第一個“10”組合后將其變?yōu)椤?1”組合，同時將其左邊的所有“1”全部移動到數(shù)組的最左端。

當(dāng)?shù)谝粋€“1”移動到數(shù)組的n-m的位置，即n個“1”全部移動到最右端時，就得到了最后一個組合。

例如求5中選3的組合：

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

4. 參考資料
(1) http://m.fzitv.net/article/54441.htm
(2) http://m.fzitv.net/article/54443.htm
(3) 組合算法

本程序的思路是開一個數(shù)組，其下標(biāo)表示1到m個數(shù)，數(shù)組元素的值為1表示其下標(biāo)代表的數(shù)被選中，為0則沒選中。

首先初始化，將數(shù)組前n個元素置1，表示第一個組合為前n個數(shù)。

然后從左到右掃描數(shù)組元素值的“10”組合，找到第一個“10”組合后將其變?yōu)?“01”組合，同時將其左邊的所有“1”全部移動到數(shù)組的最左端。

當(dāng)?shù)谝粋€“1”移動到數(shù)組的m-n的位置，即n個“1”全部移動到最右端時，就得到了最后一個組合。

例如求5中選3的組合：
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

您可能感興趣的文章: