学步园

以前发现王晓东那本书上产生全排的算法并不太好。
书中代码如下：

#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);
              }
       }
}