全排列递归算法_全排列递归算法

全排列递归算法_全排列递归算法一.全排列算法首先:什么是全排列=》百度一下从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。公式:全排列

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一.                                 全排列算法

首先:什么是全排列=》百度一下

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

公式:全排列数f(n)=n!(定义0!=1)

 

算法:递归算法=》网络上偷了一个图

 全排列递归算法_全排列递归算法

全排列:顺便复习一个数学公式

排列的定义:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 A(n,m)表示。

 

计算公式:全排列递归算法_全排列递归算法

 

组合的定义:从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。

计算公式:  ;C(n,m)=C(n,n-m)。(n≥m)

 全排列递归算法_全排列递归算法

排列和组合的区别:

看问题是否和顺序有关。有关就是排列,无关就是组合。 排列:比如说排队问题甲乙两人排队,先排甲,那么站法是甲乙,先排乙,那么站法乙甲,是两种不同的排法,和先排还是后排的顺序有关,所以是A(2,2)=2种

组合:从甲乙两个球中选2个,无论先取甲,在是先取乙,取到的两个球都是甲和乙两个球,和先后取的顺序无关,所以是C(2,2)=1种

 

#include<iostream>
using namespace std;
//交换
void swap(int &a , int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
 } 
 //全排列递归算法
void Perm(int list[] , int k ,int m) 
{
	//list 数组存放排列的数,K表示层 代表第几个数,m表示数组的长度
	if(k==m)
	{
		//K==m 表示到达最后一个数,不能再交换,最终的排列的数需要输出;
		for(int i=0 ;i<=m ;i++)
		 cout<<list[i];
		 cout<<endl; 
	 } 
	 else{
	 	for(int i=k;i<=m;i++)
	 	{
	 		swap(list[i],list[k]);
	 		Perm(list,k+1,m);
	 		swap(list[i] , list[k]);
		 }
	 }
	 
}
int main(void)
{
   int a[]={1,2,3};
   int m=2;
   Perm(a,0,2);
	/*
  123
  132
  213
  231
  321
  312
*/
 } 

算法解析思路树解释

 全排列递归算法_全排列递归算法

每次固定几位数,最后只剩一位数,输出,在从后面递归返回上一层,交换在输出

 

        for(int i=k;i<=m;i++)

             {

                    swap(list[i],list[k]);

                    Perm(list,k+1,m);

                    swap(list[i] , list[k]);

               }

代码解析”” int i=k K表示固定了几位数,当前数组交换的临界的位置

 1,2,3,4 当K=0的时候 {1,2,3,4} =》1是固定的 K+1递归

{1}p{2,3,4},K=1,I=1 数组交换只能list[1],list[2],list[3]交换 k=i ,就是为了作为一个标识。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166606.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号