排列组合算法

时间:2021-09-08 11:05:58

题目:求(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);
}
}