一． 全排列算法
首先：什么是全排列=》百度一下
从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 ,就是为了作为一个标识。
网友评论