刘汝佳在算法竞赛入门经典，http://book.douban.com/subject…，的 118 页提到生成一个可重集的全排列问题，跟上次的 生成一个字符串的全排列 很相像，但是写法却巧妙很多

#include <stdio.h>

void quick_sort(int a[], int left, int right)
{
	int i=left, j=right;
	int povit = a[(i+j)/2];
	while (i <= j)
	{
		while (a[i] < povit)
		{
			i++;
		}
		while (a[j] > povit)
		{
			j--;
		}
		if (i <= j)
		{
			int tmp = a[j];
			a[j] = a[i];
			a[i] = tmp;
			i++;
			j--;
		}
	}
	if (left < j)
	{
		quick_sort(a, left, j);
	}
	if (i < right)
	{
		quick_sort(a, i, right);
	}
}

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

int main()
{
	int n;
	while (scanf("%d", &n) != EOF)
	{
		int *p = new int[n];
		for (int i=0; i<n; i++)
		{
			scanf("%d", &p[i]);
		}
		quick_sort(p, 0, n-1);
		int *a = new int[n];
		print_permutation(n, p, a, 0);
		delete[] p;
		delete[] a;
	}
	return 0;
}

输入输出

3
1 2 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
3
1 2 2
1 2 2
2 1 2
2 2 1

需要说明的是，他的这种全排列生成需要数组有序，于是顺便就当作复习了一遍快排了