排列與組合的算法實作

由于老師提出了全排列問題。我心血來潮，将組合也弄了一下。現在寫篇日志記錄一下。

全排列

目前我所知道的全排列算法有三種，下面一一介紹：

（1）分治算法：這個算法利用了分而治之的思想。我們先從2個數開始，比如說4,5，他們的全排列隻有兩個45和54。如果在前面加個3,那麼全排列就是345,354,也就是3(54)，括号表示裡面的數的全排列。當然還有4(35)，5(34)...寫到這裡，各位看官應該已經看出點門道了吧。三個數的全排列，可以分為三次計算，第一次計算3和(45)的全排列，第二次計算4和(35)的全排列.....也就是說，将序列第一個元素分别與它以及其後的每一個元素代換，得到三個序列，然後對這些序列的除首元素外的子序列進行全排列。思想其實還是挺簡單的：

代碼實作如下：

Code:

//input 8 12.61s consumed
//input 8 11.72s consumed remove '-' in the printed array
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LENGTH 27
int n=0;
void permute(int[],int,int);
void swapint(int &a,int &b);
void printIntArray (int[],int);
//Function Implementation
void swapint(int &a,int &b){
int temp;
temp = a;
a = b;
b = temp;
}
void printIntArray(int target[],int length){
int i;
for (i=0;i<length;i++) printf ("%d",target[i]);
printf ("/n");
}
void permute(int target[],int begin,int end){
if (begin==end) {
printIntArray(target,end+1);
n++;
return;
}
int i;
for (i=begin;i<=end;i++){
swapint(target[begin],target[i]);
permute(target,begin+1,end);
swapint(target[begin],target[i]);
}
}
//test Functions
void testPermute(){
int len;
scanf ("%d",&len);
int *testcase =(int *)malloc(len*sizeof(int));
int i;
for (i=0;i<len;i++) testcase[i]=i+1;
permute(testcase,0,len-1);
}
//Main Function
void main(){
testPermute();
printf ("n=%d",n);
}

需要注意的是交換了元素，然後進行遞歸對子序列進行全排列之後，需要将元素的位置換回來。這是為了要還原現場，也就是說遞歸函數permute的形參target數組在記憶體中隻有一個，遞歸調用的時候，入棧的隻是一個數組指針，遞歸對子序列進行全排列之後，必定會對原序列造成一定的亂序。是以每次遞歸之後，都需要還原現場。

當然還有一個方法是将數組放在一個結構體中，而且還不能使用指針哦。參數調用的時候也不能使用引用。這樣遞歸的時候，記憶體中才會生成新的結構體，當然也有新的數組了。就不會影響其他的操作，不過可想而知，這樣寫多浪費記憶體空間，當然也浪費時間。

（2）字典序列算法

字典序列算法是一種非遞歸算法。而它正是STL中Next_permutation的實作算法。我們來看看他的思路吧：

它的整體思想是讓排列成為可遞推的數列，也就是說從前一狀态的排列，可以推出一種新的狀态，直到最終狀态。比如說，最初狀态是12345，最終狀态是54321。其實我覺得這跟我們手動做全排列是一樣的。首先是12345，然後12354，然後12435，12453....逐漸地從後往前遞增。

看看算法描述：

首先，将待排序列變成有序（升序）序列。

然後，從後向前尋找，找到相鄰的兩個元素，Ti<Tj，（j=i+1)。如果沒有找到，則說明整個序列已經是降序排列了，也就是說到達最終狀态54321了。此時，全排列結束。

接着，如果沒有結束，從後向前找到第一個元素Tk，使得Tk>Ti(很多時候k=j)，找到它，交換Ti跟Tk，并且将Tj到Tn(Tn是最後一個元素)的子序列進行倒置操作。輸出此序列。并回到第二步繼續尋找ij.

算法是很清晰的。看看代碼：

Code:

#include <stdio.h>
#include <stdlib.h>
//function definition
void Swap(int &a,int &b);
void Reverse (int[],int,int);
void printArray (int[],int);
int nextPermutation(int[],int);
void Swap(int &a,int &b){
int tmp;
tmp=a;
a=b;
b=tmp;
}
void Reverse(int target[],int begin,int end){
while (begin<end){
Swap(target[begin],target[end]);
begin++;
end--;
}
}
//function implementation
int nextPermutation(int target[],int end){
int i,j;
for (i=end-1;i>=0;i--)
if (target[i]<target[i+1]) break;
if (i<0) return 0; //means the permutation is over
j=i+1;
int k;
for (k=end;target[k]<=target[i];k--);
Swap(target[i],target[k]);
Reverse(target,j,end);
return 1;
}
void printArray (int target[],int length){
int i;
for (i=0;i<length;i++) printf ("%d-",target[i]);
printf ("/n");
}
//test function
void testPermute(){
printf ("input a number:");
int n;
scanf ("%d",&n);
int i;
int * testcase = (int*)malloc(n*sizeof(int));
for (i=0;i<n;i++) testcase[i]=i+1;
printArray (testcase,n);
while (nextPermutation(testcase,n-1)){
printArray (testcase,n);
}
}
//main function
void main(){
testPermute();
}

代碼完全按照算法來做，大家應該不難看懂。我就不廢話了。

（3）深搜回溯算法

深度搜尋，判重，回溯，這個算法應該算是一個基礎了。其中八皇後問題是它的經典應用。說實話感覺它就像個萬金油一樣，在啥地方都能使，但是就是不一定好使就對了。不過還是要實作一下。

其實細想一下，全排列跟八皇後問題是一樣一樣的。也是窮舉一個數列，隻是八皇後對數列的條件跟嚴格，也即是判重函數不同而已。沒有差別的。看看代碼：

Code:

//n=8 Time Consumed 11.78s
#include <stdio.h>
#include <stdlib.h>
//function definition
void printArray (const int[],int);
bool isExist(const target[],int);
void permute(int[],const int,int);
//function implementation
void printArray(const int target[],int n){
int i;
for (i=0;i<n;i++)
printf ("%d",target[i]);
printf ("/n");
}
bool isExist(const int target[],int pos){
if (pos==0) return false;
int i;
for (i=0;i<pos;i++)
if (target[i]==target[pos]) return true;
return false;
}
void permute (int target[],const int n,int i){
if (i==n) {
printArray(target,n);
return;
}
for (target[i]=1;target[i]<=n;target[i]++)
if (isExist(target,i) == false) permute(target,n,i+1);
//target[i]=1;
return;
}
//test functions
void testPermutation(){
int n;
printf ("Input a Number:");
scanf ("%d",&n);
int * testcase=(int*)malloc(n*sizeof(int));
int i;
for (i=0;i<n;i++) testcase[i]=1;
permute(testcase,n,0);
}
//main function
void main(){
testPermutation();
}

注意，我在遞歸函數permute中，回溯甚至沒有将當時位置上的數消掉。看被注釋掉的target[i]=1。而是直接在for循環中添加初始語句target[i]=1。這就表示說隻要進行深一步搜尋，都先将下一位置的數初始化掉。這樣就不用在回溯時對目前位置的錯誤值進行處理了。更加簡化了。

再看看非遞歸版的，也就是使用堆棧的形式：

Code:

// when n=8 time consumed 11.77s
#include <stdio.h>
#include <stdlib.h>
//function definition
void permute(int [],int);
void printArray(const int[],const int);
bool isExist(const int[],const int);
//function implementation
void printArray(const int target[],const int n){
int i;
for (i=0;i<n;i++)
printf ("%d",target[i]);
printf ("/n");
}
bool isExist(const int target[],int pos){
if (pos==0) return false;
int i;
for (i=0;i<pos;i++)
if (target[i]==target[pos]) return true;
return false;
}
void permute(int stack[],int n){
int sp=0; //stack pointer
while (sp>=0) {
stack[sp]++;
while (stack[sp]<=n && isExist(stack,sp)==true ) stack[sp]++;
if (stack[sp]<=n) {
//when stack is full,output the result
//and then backtrack
if (sp==n-1) {
printArray(stack,n);
sp--;
}
else {
//push stack, which means search foward
sp++;
stack[sp]=0;
}
}
else {
//backtrack
sp--;
}
}
return;
}
//test function
void testPermutation(){
int n;
printf ("Input a Number:");
scanf ("%d",&n);
int i;
int * testcase=(int*)malloc(n*sizeof(int));
for (i=0;i<n;i++) testcase[i]=0;
permute(testcase,n);
}
//main function
void main(){
testPermutation();
}

非遞歸形式算法思想是一樣的，不過就是需要自己來維護一個堆棧。注意在循環中，需要首先對堆棧元素進行自加操作，不然的話，回溯之後，就不會改變堆棧值，而使程式陷入死循環。不過當然，你要使用do while來代替這種寫法，那當然也是沒有問題的。

我隻是想說，隻要是遞歸形式的算法，都可以用堆棧來實作非遞歸的形式。大家不妨來探讨一下這個一一對應的轉換的具體形式。

組合

關于組合，我有一個比較帥的算法，在這裡跟大家分享一下。呵呵。

這是非遞歸的算法，我感覺跟全排列的字典序列算法思想上比較像。

你看它是怎麼實作的：

求n個數中的m個數的組合。

首先，初始化一個n個元素的數組（全部由0，1組成），将前m個初始化為1，後面的為0。這時候就可以輸出第一個組合了。為1的元素的下标所對應的數。

算法開始：從前往後找，找到第一個10組合，将其反轉成01，然後将其前面的所有1，全部往左邊推，即保證其前面的1都在最左邊。然後就可以按照這個01序列來輸出一個組合結果了。

而如果找不到10組合，就表示說所有情況都輸出了，為什麼？你想，（以n=5,m=3為例）一開始是11100，最後就是00111，已經沒有10組合了。

這種将問題轉換為01序列（也就是真假序列）的想法值得我們考慮和借鑒。

最後看看實作代碼：

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int l=0;
//function definition
void composition(const char [],int,int);
void printCompostion(const char[],const bool[],int);
//function implementation
void printCompostion(const char source[],const bool comp[],int n){
int i;
for (i=0;i<n;i++)
if (comp[i]==true) printf ("%c-",source[i]);
printf ("/n");
}
void compostion(const char* source,int n,int m){
bool * comp = (bool*)malloc(n*sizeof(bool));
int i;
for (i=0;i<m;i++) comp[i]=true;
for (i=m;i<n;i++) comp[i]=false;
printCompostion(source,comp,n);
l++;
while(true){
for (i=0;i<n-1;i++)
if (comp[i]==true&&comp[i+1]==false) break;
if (i==n-1) return; //all the compostion is found out
comp[i]=false;
comp[i+1]=true;
int p=0;
while (p<i){
while (comp[p]==true) p++;
while (comp[i]==false) i--;
if (p<i) {
comp[p]=true;
comp[i]=false;
}
}
printCompostion(source,comp,n);
l++;
}
}
//test function
void testCompostion(){
char* testcase = "abcdefghijklmno";
int n=strlen(testcase);
int m=7;
compostion(testcase,n,m);
}
//main function
void main(){
testCompostion();
printf ("total=%d/n",l);
}

01序列我是用bool類型來實作的。盡可能地少占用記憶體吧。而在實作将1往左移的步驟時，我是采用了将左邊的0跟右邊的1相調換的思想。

關于組合大家如果有更好的方法，不妨跟貼讨論哦。

（完）

排列與組合的算法實作

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希