Question

排列组合问题怎么解决

Answer 1

找本C/C++的书，看看公式，套着写。

以在n个数中选取m(0<m<=n)个数为例，问题可分解为：
1.
首先从n个数中选取编号最大的数，然后在剩下的n-1个数里面选取m-1个数，直到从n-(m-1)个数中选取1个数为止。
2.
从n个数中选取编号次小的一个数，继续执行1步，直到当前可选编号最大的数为m。

下面是递归方法的实现：
///
求从数组a[1..n]中任选m个元素的所有组合。
/// a[1..n]表示候选集，n为候选集大小，n>=m>0。
///
b[1..M]用来存储当前组合中的元素(这里存储的是元素下标)，
///
常量M表示满足条件的一个组合中元素的个数，M=m，这两个参数仅用来输出结果。

void combine( int a[], int n, int m, int b[], const int M )
{
int
i,j;
for(i=n; i>=m; i--) // 注意这里的循环范围
{
b[m-1] = i - 1;

if (m > 1)
combine(a,i-1,m-1,b,M);
else // m
== 1, 输出一个组合
{
for(j=M-1; j>=0; j--)
printf("%d ",
a[b[j]]);
}
}
}

下面加入排列，就是对上面选取的组合进行全排列，下面是主函数以及子函数，通过测试。

＃i nclude <stdio.h>

#define MAX_N 5

void full_permutation(int l, int *num, int *rcd, int *used)

{

int i;
int X_N=3;
int path_ij[3];

if (l == X_N)
{
for (i=0; i<X_N;
i++)
{
path_ij[i]=rcd[i];
printf("%d", path_ij[i]);
if (i
< X_N-1)
printf(" ");
}
printf("\n");
return;

}

for (i=0; i<X_N; i++) //枚举所有的数（n个），循环从0开始
if (!used[i])
//若num[i]没有使用过，则
{
used[i] = 1; //标记为已使用
rcd[l] = num[i];
//在l位置放上该数
full_permutation(l+1, num, rcd, used); //填下一个位置
used[i] = 0;
//清标记
}

}

void combine( int a[], int n, int m, int b[], const int M )
{
int
temp[3];
int rcd[3]; //记录每个位置填的数
int used[3]; //标记数是否用过

int i,j, k;
for(i=n; i>=m; i--) // 注意这里的循环范围
{
b[m-1] = i
- 1;
if (m >
1)
combine(a,i-1,m-1,b,M);
else // m == 1,
输出一个组合
{
for(j=M-1; j>=0;
j--)
{
temp[M-1-j]=a[b[j]];
}
for (k=0; k<3;
k++)
{
used[k] = 0;
}
full_permutation(0, temp, rcd,
used);
}
//printf("%d", i);
}
}

void main()

{
int i; //共n个数
const int N = MAX_N;
const int M = 3;
int
b[3] ;
int num[5]; //存放输入的n个数

for (i=0; i<MAX_N; i++)
{
num[i] = i+1;
}

combine(num,N,M,b,M);

}