刘汝佳在算法竞赛入门经典,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
需要说明的是,他的这种全排列生成需要数组有序,于是顺便就当作复习了一遍快排了