组合数学-next_permutation全排列_next_permutation函数水星人-程序员宅基地

竞赛中关于排列问题可能会使用到next_permutation函数的一个全排列，但是仍然需要掌握基本的排列的递归写法，下面简单介绍一下用法。（直到如何使用即可）

next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止。
prev_permutation函数与之相反，是生成给定序列的上一个较小的排列。二者原理相同，仅遍例顺序相反

1.STL中的next_permutation 用法
2.全排列的递归写法

1.使用STL里面的函数进行全排列：（全排列前要需要排序才行）

数字排序：

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    
	char a[] = {
    1,2,3};
	sort(a,a+3);
	do{
    
		for(int i = 0;i < 3;i++) printf("%d ",a[]);
		printf("\n");
	}while(next_permutation(a,a+3));
	return 0;
}

输出结果：

字符串全排列：

#include<stdio.h>
#include<algorithm>
using namespace std;
//int cmp(const void *a,const void *b){
    
//	return *(char *)a-*(char *)b;
//}
int main(){
    
	char a[] = "132";
	sort(a,a+3);//C++
//	qsort(a,3,sizeof(a[0]),cmp);//C 
	do{
    
		printf("%s\n",a);
	}while(next_permutation(a,a+3));
	return 0;
}

输出结果：

结构体的全排序
解释一下，结构体也可以通过写 cmp 函数实现全排列，

next_permutation（node,node+n,cmp）

也可以借助下标进行全排列

#include<stdio.h>
#include<algorithm>
using namespace std;
const int Maxn = 3;
struct Node{
    
	int x;
}a[100];
int q[100];
int main(){
    
	for(int i = 1;i <= Maxn;i++){
    
		a[i].x = q[i] = i;	//让结构体元素按照正常顺全排列 
//		a[Maxn-i+1] = q[i] = i;	//顺序将会相反 
	}
	do{
    
		for(int i = 1;i <= Maxn;i++) printf("%d ",a[q[i]].x);
		printf("\n");
	}while(next_permutation(q+1,q+Maxn+1));
	return 0;
}

这个是STL中的源码可以参考一下，它的是非递归写法，下面会说到递归写法。参考链接
在这里插入图片描述

2.全排列的递归写法

#include <iostream>
using namespace std;
void get_permutation(char *a, int idx, int length)	//左下标和长度值，从头循环到尾
{
    
    if (idx == length-1){
    
        for (int i=0; i<length; ++i)
            printf("%s ",a);
        printf("\n");
    }
    else {
    
        for (int i=idx; i<length; ++i){
    
            swap(a[i],a[idx]);
            get_permutation(a,idx+1,length);
            swap(a[i],a[idx]);
        }
    }
}
int main()
{
    
    char array[] = "123";
    get_permutation(array,0,3);
    return 0;
}

输出结果：

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

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

简单用法就是上面局的例子，时间复杂度是在 O(n!) ~ O(n∗n!) 之间，还是比较花时间的，所以慎用（蓝桥杯中用法会比较多）
参考链接

本文链接：https://blog.csdn.net/qq_53269459/article/details/121091366

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

php 编译 pdo_mysql_Linux正确编译pdo_mysql扩展-程序员宅基地

文章浏览阅读280次。错误编译pdo_mysqlphp扩展的操作流程，以及解决错误并成功完成编译pdo_mysql新编译的PHP环境运行项目时报错PHP Fatal error: Undefined class constant 'MYSQL_ATTR_INIT_COMMAND'原因是没有加载pdo_mysql扩展错误配置pdo_mysql及编译cd ext/pdo_mysqlphpize./configure --w..._/usr/local/php7.4.24/ext/pdo_mysql/php_pdo_mysql_int.h:29:11: fatal error: m

Mybatis入参_mybatis select参数对象-程序员宅基地

文章浏览阅读332次。<!-- 关于sql语句中填充占位符时参数的处理： 1.单个参数：MyBatis不做任何处理，填充占位符时获取参数的key可以任意指定如：#{任意指定} 2.多个参数：MyBatis会将多个参数封装到一个Map中，Map的key时arg0,arg1,arg2...或者param1,pa..._mybatis select参数对象

Maven上传问题-手动与401_mvn 本地上传jar,401-程序员宅基地

文章浏览阅读1.4k次。Maven上传问题注意: 如非必要, 请不要手动上传jar包, 手动上传如果遗漏pom文件, 会导致jar包内的pom依赖丢失, 这样上传的包在被使用时会产生依赖丢失的报错私服jar包结构手动上传的jar生成的pom原始pom1.手动上传快照版本maven不支持手动上传snapshot版本jar包到nexus, 当需要上传快照版本时, 需要用命令上传1.配置 maven安装目录conf/settings.xml(注意此处是安装目录的setting.xml,不是.m2下的,而且由于我们命令_mvn 本地上传jar,401

vue中css样式只在当前vue中生效_vue怎么让css只在此页面显示-程序员宅基地

文章浏览阅读4.2k次，点赞2次，收藏3次。在设置style时，会影响到其他组件样式，为避免样式共享，可在样式style标签里添加scoped 即可_vue怎么让css只在此页面显示

datax-web在windows上环境搭建及同步数据测试_datax-web job execute end(finish) -----------<br>--程序员宅基地

文章浏览阅读8.6k次，点赞7次，收藏44次。datax-web部署说明：datax-web是一个集成datax和xxljob定时任务优秀的同步数据库开源框架。data-web开源地址：https://github.com/WeiYe-Jing/datax-web DataX 是阿里巴巴集团内被广泛使用的离线数据同步工具/平台，实现包括 MySQL、Oracle、SqlServer、Postgre、HDFS、Hive、ADS、HBase、TableStore(OTS)、MaxCompute(ODPS)、DRDS 等各种异构数据源之间高效的数._datax-web job execute end(finish) ---------------------- returnt:returnt

MYSQL, mybatis 如何使用自增主键_mybatis auto_increment-程序员宅基地

文章浏览阅读2.5k次。通常我们在应用中对mysql执行了insert操作后，需要获取插入记录的自增主键。本文将介绍java环境下的4种方法获取insert后的记录主键auto_increment的值：通过JDBC2.0提供的insertRow()方式通过JDBC3.0提供的getGeneratedKeys()方式通过SQL select LAST_INSERT_ID()函数通过SQL @@IDENTITY 变量1.通过JDBC2.0提供的insertRow()方式自jdbc2.0以来，可以通过下面的方式执._mybatis auto_increment

随便推点

材质面向摄像机_ue5 通过材质使面片始终朝向摄像机-程序员宅基地

文章浏览阅读2.4k次，点赞2次，收藏10次。材质面向摄像机单贴图面向摄像机组合贴图面向摄像机单贴图面向摄像机主要是调用RotateAboutAxis这个材质函数输入旋转轴 001计算旋转角度去除camera的z轴影响算出物体到摄像机的向量归一化后算出夹角FVector::Rotation()函数的内部实现（局部）FRotator R; // Find yaw.R.Yaw = FMath::Atan2(Y,X) * (180.f / PI); // Find pitch.R.Pitch = FMath_ue5 通过材质使面片始终朝向摄像机

轻松搞定 android MVP 架构、okHttp 网络模块封装的项目_android mvp网络封装-程序员宅基地

文章浏览阅读373次。CommonMvp MVP 框架的使用commonMvp 能做什么？1、mvp 实现 model view presenter 业务和界面解耦2、整合网络请求3、简化网络调用流程4、整合状态栏和标题栏实现沉浸式状态栏5、Activity 、Fragment 中使用方法一致接口式封装生命周期1、有问题请提交 isuue/(QQ:194093798) 谢谢大家持续更新2、为新手提供一个可靠可用的 mvp 框架结构集成allprojects { repos_android mvp网络封装