题目:求(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 <stdio.h>
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;
}
二、组合算法:
组合就是从n个数中选m个数的所有组合。(n>=m)
利用递归的思想,假设从n=4,m=2,数组a{1,2,3,4},则算法思想如下图所示:
上图中,第一层S1中的节点是数组中的所有数字,第二次S2中的节点是分别从父节点的下一个位置开始。因为这个例子中m=2,所以共有2层。从第一层到第二层,深度遍历这颗树,即可得到所有组合。
递归算法代码:
#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);
}
}
相关推荐
主要介绍了C#实现排列组合算法的完整实例,文中实例主要展示了排列循环方法和排列堆栈方法,需要的朋友可以参考下
PHP实现多种类型的排列组合算法,PHP多种方式实现排列组合算法。非常有用,欢迎下载。
该文档对排列组合问题的算法设计问题进行一系列讲述
排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。
Java排列组合算法 - 郭睿的专栏 - CSDN博客Java排列组合算法 - 郭睿的专栏 - CSDN博客
排列组合 排列 组合 java排列组合算法 排列组合算法
排列组合公式排列组合计算公式[规整].pdf
本程序是排列组合算法的c语言表示,使用递归实现
excel VBA - 排列组合生成算法 - ,可快速生成指定项目的所有排列组合
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
排列组合算法排列组合算法.doc
Java排列组合算法
c++课程设计,排列组合,算法 超级简单的,
排列组合公式排列组合计算公式.doc
主要介绍了Python实现的简单排列组合算法,涉及Python使用itertools库进行排列组合运算相关操作技巧,需要的朋友可以参考下