排列组合算法
题目:求(1)一组数字的全排列(2)一组数字中某几个数字的组合
一、排列算法:
全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3}为例说明如何编写全排列的递归算法。 如下图所示:
上图中,第一层S1表示第一个数分别与第1、2、3个数交换位置,如123是1和第一个数1交换,213是1和第二个数2交换,321是1和第三个数交换。第二层S2是第二个数分别与第2、3个数交换位置。则最后一层的所有叶子节点,即为全排列的所有结果。第k层中的节点Sk就是父节点中的第k个数,分别与第k、k+1...n个数交换位置。
递归算法代码:
#include <iostream>
int n =0;
void swap( int* a,int* b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[],int k,int m)
{
int i;
if(k > m)
{
for (i = 0; i <= m; i++)
{
printf("%d ", list[i]);
}
printf( "\n" );
n++;
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}
int main()
{
int list[] = { 1 , 2 , 3 , 4 , 5};
perm(list, 0 , 4);
printf("total:%d\n", n);
return 0 ;
}
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210818210032488-316619184.png)
#include <vector>
#include <iostream>
using namespace std;
void Comb(int index,int begin,int len,int n,int * A,int* C);
int main()
{
int A[5] = {1,2,3,4,5};
int len =5, n =3;
int* C =new int[n +1];
Comb(0,0, len, n, A, C);
delete[]C;
return 0;
}
//递归组合
void Comb(int index,int begin,int len,int n,int * A,int * C)
{
// index表示某个组合中的索引,begin表示从数组A中begin位置开始寻找,
// len表示数组A长度,n表示组合中个数,A表示原数组,C表示组合数组
if(index == n)
{
for (int i = 0; i < n; i++)
{
cout << C[i] <<"";
}
cout << endl;
return ;
}
for(int j = begin; j <= len - n + index; j++)
{
C[index] = A[j];
Comb(index +1, j +1, len, n, A, C);
}
}
相关文章
- Java实现 蓝桥杯 算法训练VIP 报数(暴力+数学)约瑟夫环问题
- Java实现 蓝桥杯VIP 算法提高 质数的后代
- Java实现 蓝桥杯VIP 算法提高 11-2删除重复元素
- 人工神经网络算法的学习率有什么作用
- 简单易学的机器学习算法—SVD奇异值分解
- [算法]Bobmer
- ML之回归预测:利用十类机器学习算法(线性回归、kNN、SVM、决策树、随机森林、极端随机树、SGD、提升树、LightGBM、XGBoost)对波士顿数据集回归预测(模型评估、推理并导到csv)
- 基于粒子群优化算法的冷热电联供型综合能源系统运行优化(Matlab代码实现)
- 【控制模型】数字 PID 控制 — 增量式PID算法
- 智能优化算法:足球联赛竞争算法-附代码
- 排列组合相关算法 python
- orb 算法源码实现
- 学习算法笔记(10)
- 逆向分析之定位算法的一些经验
- 在OpenCV里使用K均值聚类算法
- 算法——dfs 判断是否为BST