以前发现王晓东那本书上产生全排的算法并不太好。
书中代码如下:
#include <iostream>
using namespace std;
template <class Type>
inline void Swap(Type &a,Type &b)
{
Type temp=a;a=b;b=temp;
}
template <class Type>
void Perm(Type list[],int k,int m)
{
if(k==m)
{
for(int i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
else
for(int i=k;i<=m;i++)
{
Swap(list[k],list[i]);
Perm(list,k+1,m);
Swap(list[k],list[i]);
}
}
最明显的一个问题是,这个程序生成的全排并不是字典序的。这里还要提一提编程实践起到的作用。要不是当初在机器上运行了一遍,还不知道这个问题呢。简单测试一下,你会发现输入为1,2,3时,最后的两个结果是3,2,1, 3,1,2 这两个的位置明显相反,应该是输入的倒序3,2,1作为最后一个排列。输入1,2,3,4问题就更明显了。
现在采用另一种方法来生成全排:
const int N = 4;
bool used[N + 1];
void perm(int a[],int k,int n)
{
if (k == n)
{
for (int i = 0; i < n; i++)
cout << a[i] << ' ';
cout << endl;
}
else
{
int i;
for (i = 1; i <= n; i++)
if(!used[i])
{
used[i] = true;
a[k] = i;
perm(a,k + 1,n);
used[i] = false;
}
}
}
int main()
{
for (int i = 0; i <= N; i++)
used[i] = false;
int a[N];
perm(a,0,N);
system("PAUSE");
return 0;
}
这个程序能产生字典序排列的全排,但是还不能生成多重集的全排。再改一下下。
对集合S的元素进行排序,然后统计各个元素出现的个数,可以得到生成可重集的程序(一下程序出自刘汝佳的书):
#include<stdio.h>
// 输出数组P中元素的全排列。数组P中可能有重复元素, 数组P中的元素需要已经按顺序排好了
void print_permutation(int n, int* P, int* A, int cur)
{
int i, j;
if (cur == n)
{
for (i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n");
}
else for (i = 0; i < n; i++) //因为是全排列,所以每次大循环是必要的。从中选去最小元素
if (!i || P[i] != P[i-1])
{
int c1 = 0, c2 = 0;
for (j = 0; j < cur; j++)
if (A[j] == P[i]) c1++; //判断该元素是否还能使用
for (j = 0; j < n; j++)
if (P[i] == P[j]) c2++;
if (c1 < c2)
{
A[cur] = P[i];
print_permutation(n, P, A, cur+1);
}
}
}