首页 > 其他 > 详细

全排列问题

时间:2015-04-21 20:44:08      阅读:365      评论:0      收藏:0      [点我收藏+]

字符串全排列算法 

设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}

ri+Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。

(1)当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素。

(2)当n>1时,Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),...,(rn)+Perm(Rn)构成。

此算法就是按照上述思想来设计的。不难想出,此算法使用递归思想比较容易实现。

设Perm(list,k,m)递归地产生所有前缀是list[0:k-1],且后缀是list[k:m]的全排列的所有排列。

那么调用算法Perm(list,0,n-1)则产生list[0:n-1]的全排列。

算法的实现代码如下:
注:在main()函数中调用Perm(s,0,strlen(s)-1)
#include <iostream>
using namespace std;

void Swap(char &s1,char &s2)
{
	char temp=s1;
	s1=s2;
	s2=temp;
}

void Perm(char s[],int k,int m)
{
	if(k==m)
		cout<<s<<endl;
	else
	{
		for(int i=k;i<=m;i++)
		{
			Swap(s[k],s[i]);
			Perm(s,k+1,m);
			Swap(s[k],s[i]);
		}
	}
}

int main()
{
	char s[]="abcd";
	Perm(s,0,strlen(s)-1);
	return 0;	
}

程序运行结果:
技术分享

全排列问题

原文:http://blog.csdn.net/sxhlovehmm/article/details/45175271

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!