天天看點
傳回

排列組合總結組合全排列：

組合

1.位運算實作求組合：

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

00000---------null

00001---------a

00010 --------b

00011---------ab

00100---------c

… …

11111--------abcde

給出程式如下所示：

#include <stdio.h>
#include <string.h>

void printCombination(char* str, int i);
void combination(char* str)
{
	int len = strlen(str);
	//共有(1<<len)個組合，其中有一次什麼都不列印外
	for(int i=0; i< (1<<len); ++i)
	{
		printCombination(str, i);
		printf("\n");
	}
}

void printCombination(char* str, int i)
{
	int len = strlen(str);
	for(int j=0; j<len; ++j)
	{
		//看s中哪些位為
		int s = i&(1<<j);
		if(s)
			printf("%c", str[j]);
	}
}	

int main()
{
	char str[] = "abc";
	combination(str);
}

2.遞歸的思路解決 

#include <stdio.h>
#include <string.h>

void printCombination(char* str, int len, int m, int* arr, const int M);
void combination(char* str)
{
	int len = strlen(str);
	int* arr = new int[len];
	for(int i=1; i<=len; ++i)
	{
		printCombination(str, len, i, arr, i);
	}
	delete[] arr;
}
//從n中選m個數進行組合
/**************************************
a. 首先從n個數中選取編号最大的數，然後在剩下的n-1個數裡面選取m-1個數，
直到從n-(m-1)個數中選取個數為止。
b. 從n個數中選取編号次小的一個數，繼續執行步，直到目前可選編号最大的數為m。
******************************************/
void printCombination(char* str, int len, int m, int* arr, const int M)
{
	for(int i=len; i>=m;--i)
	{
		//依次選擇編号最大的數，次大的數....
		arr[m-1] = i-1;
		if(m>1)
		{
			//選擇的數目大于，從剩餘的i-1個數中選取m-1個數的組合
			printCombination(str,i-1,m-1,arr,M);
		}
		else
		{
			//列印M個數字
			for(int j=M-1; j>=0; --j)
			{
				printf("%c ", str[arr[j]]);
			}
			printf("\n");
		}
	}
}	

int main()
{
	char str[] = "abcd";
	combination(str);
	return 0;
}

3.非遞歸實作

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

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

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

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

例如求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

實作代碼如下：

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

全排列：

1. 遞歸

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

代碼實作如下：

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

2. 字典序

有時候遞歸的效率使得我們不得不考慮除此之外的其他實作，很多把遞歸算法轉換到非遞歸形式的算法是比較難的，這個時候我們不要忘記了标準模闆庫已經實作的那些算法，這讓我們非常輕松。STL有一個函數next_permutation()，它的作用是如果對于一個序列，存在按照字典排序後這個排列的下一個排列，那麼就傳回true且産生這個排列，否則傳回false。注意，為了産生全排列，這個序列要是有序的，也就是說要調用一次sort。

直接用STL上的 

#include "iostream"
#include "algorithm"
using namespace std;

void permutation(char* str,int length)
{
	sort(str,str+length);	//必須得先排序
	do
	{
		for(int i=0;i<length;i++)
			cout<<str[i];
		cout<<endl;
	}while(next_permutation(str,str+length));

}
int main(void)
{
	char str[] = "acb";
	cout<<str<<"所有全排列的結果為："<<endl;
	permutation(str,3);
	system("pause");
	return 0;
}

其中next_permutation()的實作如下：

template<class BidirectionlIterator>
bool next_permutation(BidirectionalIterator firt, 
					  BidirectionalIterator last)

{
	if(first == last) return false;	//空區間
	BidirectionalIterator i = first;
	++i;
	if(i == last) return false;	//隻有一個元素
	i = last;	//i指向尾端
	--i;

	for(;;){
		BidrectionalIterator ii = i;
		--i;
		//以上，鎖定一組(兩個)相鄰元素
		if(*i < *ii)	//如果前一個元素小于後一個元素
		{
			BidrectionalIterator j = last;	//令j指向尾端
			while(!(*i < *--j));	//由尾端往前找，直到遇上比*i大的元素
			iter_swap(i,j);			//交換i，j
			reverse(ii, last);		//将ii之後的元素全部逆向重排
			return true;
		}
		if(i == first)				//進行到最前面了
		{
			reverse(first, last);	//全部逆向重置
			return false;		
		}
	}
}

自己設計函數next_permutation()： 

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;
//反轉數組
void reverse(char* str, int first, int last)
{
	if(str == NULL || *str == '\0')
		return;

	while(first < last)
	{
		char ch = str[first];
		str[first] = str[last];
		str[last] = ch;
		first++;
		last--;
	}
}
//列印數組
void printfString(char* str)
{
	for(int i=0; i<strlen(str); ++i)
	{
		printf("%c", str[i]);
	}
	printf("\n");
}
//找到下一個數組
bool next_permutation(char* str)
{
	if(str == NULL || *str=='\0')
		return false;

	int len = strlen(str);
	int i = len - 2;
	int ii = i+1;
	int j = len - 1;

	//從後端開始找到第一對str[i]<str[j]的數字
	while(str[i] > str[ii])
	{
		--i;
		--ii;
		//如果i<0，則表示已經全部排列
		if(i<0)
		{
			//全部翻轉
			reverse(str, i+1, len-1);
			return false;
		}
	}
	//從後面找到第一個大于str[i]的數字
	while(str[j] < str[i])
	{
		--j;
	}
	
	//交換
	char ch = str[i];
	str[i] = str[j];
	str[j] = ch;
	//翻轉j之後的數組
	reverse(str, ii, len-1);
	
	return true;
		
}



int main()
{
	char str[] = "cab";
	int len = strlen(str);
	//必須先排序
	sort(str, str + len);
	printfString(str);
	//列印全排列
	while(next_permutation(str))
	{
		printfString(str);
	}

	return 0;
}

參見：

http://blog.csdn.net/hackbuteer1/article/details/7462447

http://xiaomage.blog.51cto.com/293990/74094

http://blog.csdn.net/hackbuteer1/article/details/6657435

C/C++ 資料結構與算法 筆試面試
上一篇: Java面試題大全，解決應屆生面試難題，沒有項目經驗難題
下一篇: 原型、原型鍊的相關知識點

繼續閱讀