|
来源:www.cncfan.com | 2006-4-28 | (有7010人读过)
Author: kingwei @ ECUST
Date： 2005.8.15
E-mail: jx_kingwei@sina.com
1 排列问题
1.1 类循环排列
输入样例
3 2
输出样例
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
代码
#include <stdio.h>
#define MAX_N 10
int n, m; //相当于n重循环，每重循环长度为m
int rcd[MAX_N]; //记录每个位置填的数
void loop_permutation(int l)
{
int i;
if (l == n) //相当于进入了n重循环的最内层
{
for (i=0; i<n; i++)
{
printf("%d", rcd[i]);
if (i < n-1)
printf(" ");
}
printf("\n");
return;
}
for (i=0; i<m; i++) //每重循环长度为m
{
rcd[l] = i; //在l位置放i
loop_permutation(l+1); //填下一个位置
}
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
loop_permutation(0);
return 0;
}
实际上，这样的方法是用递归实现多重循环，本递归程序相当于n重循环，每重循环的长度为m的情况，所以输出共有m^n行。
1.2 全排列
对输入的n个数作全排列。
输入样例
3
1 2 3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
代码
#include <stdio.h>
#define MAX_N 10
int n; //共n个数
int rcd[MAX_N]; //记录每个位置填的数
int used[MAX_N]; //标记数是否用过
int num[MAX_N]; //存放输入的n个数
void full_permutation(int l)
{
int i;
if (l == n)
{
for (i=0; i<n; i++)
{
printf("%d", rcd[i]);
if (i < n-1)
printf(" ");
}
printf("\n");
return;
}
for (i=0; i<n; i++) //枚举所有的数（n个），循环从0开始
if (!used[i]) //若num[i]没有使用过，则
{
used[i] = 1; //标记为已使用
rcd[l] = num[i]; //在l位置放上该数
full_permutation(l+1); //填下一个位置
used[i] = 0; //清标记
}
}
int read_data()
{
int i;
if (scanf("%d", &n) == EOF)
return 0;
for (i=0; i<n; i++)
scanf("%d", &num[i]);
for (i=0; i<n; i++)
used[i] = 0;
return 1;
}
int main()
{
while (read_data())
full_permutation(0);
return 0;
}
程序通过used数组，标记数是否被用过，可以产生全排列，共有n!种。
但是，通过观察就会发现，若输入的n个数有重复，那么在输出的n!种排列中，必然存在重复的项，若不允许输出重复的项，该怎么做呢？
1.3 不重复排列
输入n个数，输出由这n个数构成的排列，不允许出现重复的项。
输入样例
3
1 1 2
输出样例
1 1 2
1 2 1
2 1 1
代码
#include <stdio.h>
#define MAX_N 10
int n, m; //共有n个数，其中互不相同的有m个
int rcd[MAX_N]; //记录每个位置填的数
int used[MAX_N]; //标记m个数可以使用的次数
int num[MAX_N]; //存放输入中互不相同的m个数
void unrepeat_permutation(int l)
{
int i;
if (l == n) //填完了n个数，则输出
{
for (i=0; i<n; i++)
{
printf("%d", rcd[i]);
if (i < n-1)
printf(" ");
}
printf("\n");
return;
}
for (i=0; i<m; i++) //枚举m个本质不同的数
if (used[i] > 0) //若数num[i]还没被用完，则
{
used[i]--; //可使用次数减1
rcd[l] = num[i]; //在l位置放上该数
unrepeat_permutation(l+1); //填下一个位置
used[i]++; //可使用次数恢复
}
}
int read_data()
{
int i, j, val;
if (scanf("%d", &n) == EOF)
return 0;
m = 0;
for (i=0; i<n; i++)
{
scanf("%d", &val);
for (j=0; j<m; j++)
if (num[j] == val)
{
used[j]++;
break;
}
if (j == m)
{
num[m] = val;
used[m] = 1;
m++;
}
}
return 1;
}
int main()
{
while (read_data())
unrepeat_permutation(0);
return 0;
}
本程序将全排列中的used标记数组，改为记录输入中，每个本质不同的数出现的次数，并在递归函数中使用。需要注意的是，在输入过程中，应剔除重复的数值。
实际上，重复排列的产生是由于同一个位置被多次填入了相同的数，并且这多次填入又是在同一次循环过程中完成的。本方法通过统计每个本质不同的数的个数，使得循环长度由n变为m，这样，i一旦自增，就再也不会指向原先填入过的数了。
这种方法剪去了重复项的生成，从而加快了搜索速度，是深度优先搜索中常用的剪枝技巧。
|
