前言：本期穿插讲解一些《算法与数据结构系列》（Algorithms and Data Structures，题中简称AD），此篇为第二期——组合与排列算法。
组合与排列的知识我们在高中就已经学习过了，它们的最大区别就是，如果我们在实际问题中需要考虑元素之间的顺序，就使用排列；如果不用考虑元素之间的顺序，就使用组合。
组合
所谓组合其实就是对一组物体进行无序地重新排列，例如现在有一数组[1,2,3,4]，要对其元素进行两两组合，可以得到以下六种组合：
1，2
1，3
1，4
2，3
2，4
3，4
若一共有N个元素，需要从中取出M个元素进行组合，则一共有C（N，M）=N*（N-1）*...*（N-M+1）/（1*2*...*M）=N！/[M！（N-M）！]种组合方式。
实际问题如：在一个礼品店里有种礼品，而只需要购买其中2种，一共有10*9/2=45种购买方式。
在使用计算机处理组合算法时，可以采用递归算法，即每次从原数组中取出两个元素存放到新数组中。
#include<stdio.h>
#define N 4
#define M 2
//全局变量，a为给定数组，b为存储组合的数组
int a[N];
int b[M];
//函数声明
void comb(int,int);
void print();
//打印数组b
void print()
{
int i;
for(i=0;i<M;i++) {
printf("%d ",b);
}
printf("\n");
}
//组合，递归方式
void comb(int n,int m)
{
int i;
if(m==0) {
print();
return;
} else {
for(i=n-1;i>=0;--i) {
b[m-1]=a;
comb(i,m-1);
}
}
}
int main()
{
int i;
for(i=0;i<N;i++)
a=i+1;//初始化数组
comb(N,M);
return 0;
}
全排列
假设现在给定数组1,2,3，其全排列如下所示：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
若一共有N个元素进行全排列，则一共有P（N，N）=N！种组合方式。
在编写计算机代码时，同样采取递归的算法。
#include <stdio.h>
#define N 3
int a[N]; //全局变量，数组
//函数声明
void perm(int); /*求数组的全排列 */
void print();
void swap(int, int);
//主函数
int main(){
int i;
for(i = 0; i < N; ++i){
a = i + 1;
}
perm(0);
return 0;
}
//全排列函数
void perm(int offset){
int i, temp;
if(offset == N-1){ // BaseCase
print();
return;
}else{
for(i = offset;i < N; ++i){
swap(i, offset);//交换前缀
perm(offset + 1);//递归
swap(i, offset);//将前缀换回来，继续做前一次排列
}
}
}
//打印数组
void print(){
int i;
for(i = 0; i < N; ++i)
printf(" %d ",a);
printf("\n");
}
//交换全局数组的两个指定元素
void swap(int i, int offset){
int temp;
temp = a[offset];
a[offset] = a;
a = temp;
}
来源： 张泽旺 深度学习每日摘要
智造家
