全排列 方法:全排列函数和递归和字典序

题目描述

给你一个字符串,按字典序从小到大输出这个字符串的全排列

输入

一个由小写字母组成的长度小于等于8的不含重复字符的字符串

输出

按字典序从小到大输出这个字符串的全排列

样例输入

abc

样例输出

abc
acb
bac
bca
cab
cba

1

next_permutation函数


    组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”,我们可以把它理解为序列的字典序的前后,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1.


对于next_permutation函数,其函数原型为:

     #include <algorithm>

     bool next_permutation(iterator start,iterator end)

当当前序列不存在下一个排列时,函数返回false,否则返回true

next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列,同时并改变num数组的值。

另外,需要强调的是,next_permutation()在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。

此外,next_permutation(node,node+n,cmp)可以对结构体num按照自定义的排序方式cmp进行排序。

应用举例:

#include <iostream>  
#include <algorithm>  
using namespace std;  
int main()  
{  
    int num[3]={1,2,3};  
    do  
    {  
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  
    }while(next_permutation(num,num+3));  
    return 0;  
}  


2.递归 但运行出来不是字典序  递归序

#include <iostream>
#include <string.h>
using namespace std;
void swap(char *a,int i,int j)
{
	char temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
void quanpailie(char array[],int len,int index)
{
	if(index==len)//全排列结束
	{
		cout<<array<<endl;
    }
    else
    {
    	for(int i=index;i<len;++i)
    	{
    		swap(array,index,i);//将第i个元素交换至当前index下标处 
    		quanpailie(array,len,index+1);//以递归的方式对剩下的元素进行全排列 
    		swap(array,index,i);//将第i个元素放回原处 
		}
	}
}	
int main()
{
	char array[8]={0};
	cin>>array;
	quanpailie(array,strlen(array),0);
	return 0;	
}

2.字典序

解题思路

设P是1~n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn

  1)从排列的右端开始,找出第一个比右边数字小的数字的序号j(j从左端开始计算),即 j=max{i|pi<pi+1}
  2)在pj的右边的数字中,找出所有比pj大的数中最小的数字pk,即 k=max{i|pi>pj}(右边的数从右至左是递增的,因此k是所有大于pj的数字中序号最大者)
  3)对换pi,pk

  4)再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1,这就是排列p的下一个排列。

证明


算法步骤1,得到的子串 s = {pj+1,.....,pn}, 是按照从大到小进行排列的。即有 pj+1 > pj+2 > ... > pn, 因为 j=max{i|pi<pi+1}。
算法步骤2,得到了最小的比pj大的pk,从n往j数,第一个比j大的数字。将pk和pj替换,保证了替换后的数字比当前的数字要大。
于是得到的序列为p1p2...pj-1pkpj+1...pk-1pjpk-1...pn.注意这里已经将pk替换成了pk。
这时候我们注意到比p1..pj-1pk.....,恰好比p1....pj.....pn大的数字集合。我们在这个集合中挑选出最小的一个即时所要求的下一个排列。
算法步骤3,即是将pk后面的数字逆转一下(从从大到小,变成了从小到大。)
由此经过上面3个步骤得到的下个排列时恰好比当前排列大的排列。
同时我们注意到,当所有排列都找完时,此时数字串从大到小排列。步骤1得到的j = 0,算法结束。

算法实现:

#include <iostream>
#include <string.h>
using namespace std;
void swap(char*s,int i,int j){//交换两个元素
	char temp;
	temp=s[i];
	s[i]=s[j];
	s[j]=temp;
}
void reverse(char *s, int first, int last){//翻转序列
	while (first<last){
		swap(s,first++,last--);
	}
}
int findmin(char*a){  //从排列的右端开始,找出第一个比右边数字小的数字的序号
    int j,length=strlen(a);
	for(j=length-2;j>=0;j--)
	{
		if(a[j]<a[j+1])break;
	}
	return j;
}
int main()
{
	char a[8];
	cin>>a;
	int i=0,j,k,length=strlen(a);
	for(i=0;i<length-1;i++)
	{
		for(j=i;j<length-1;j++)
		{
			if(a[i]>a[j])swap(a,i,j);
		}
	}
	cout<<a<<endl;
	while(true)
	{
        j=findmin(a);
        if(findmin(a)==-1) break;
        for(i=length-1;i>j;i--)
        {
        	if(a[i]>a[j])break;
		}
		swap(a,j,i);
		reverse(a,j+1,length-1);
		cout<<a<<endl;
	}
	return 0;
 }
版权声明:本文为qq_41486817原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41486817/article/details/80617270

智能推荐

idea基础–(7)–jsp页面Controller路径自动识别的问题“Cannot resolve controller URL ...”,Cannot resolve variable

idea之所以强大,就是强大的代码提示和联想功能,写起代码来简直不要太爽。但是这几天我发现在我的jsp页面中访问controller路径的时候不会自动提示了,对于这么严谨的我肯定要找出原因啊,哈哈。 最终效果:按住ctrl,同时点击左键会自动跳转到对应的controller代码块,爽。 需要同时满足的条件 JSP页面顶部包含如下代码: 在idea的项目设置中显示如下:  若显示的是spring a...

26_Python基础_继承

面向对象三大特性: 封装 根据 职责 将 属性 和 方法 封装 到一个抽象的 类 中 继承 实现代码的重用, 相同的代码不需要重复的编写 多态 不同的对象调用相同的方法,  产生不同的执行结果,  增加代码的灵活度 1.  单继承 1.1 概念 继承的概念:&...

循环

与任何程序设计语言一样Java利用条件语句与循环结构确定流程控制,一下总结一下Java中的循环语句: while do while for switch 对于golang来说: switch非常灵活。从第一个expr为true的case开始执行,如果case带有fallthrough,程序会继续执行下一条case,不会再判断下一条case的expr,如果之后的case都有fallthrough,d...

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

猜你喜欢

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...