欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排列组合总结

程序员文章站 2022-05-21 22:45:27
...

组合

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