枚举排列

求1~n的全排列

// 求1~n的全排列. n<100
// Rujia Liu
#include<cstdio>
using namespace std;

int A[101];

// 输出1~n的全排列
void print_permutation(int n, int* A, int cur) {
  if(cur == n) { // 递归边界
    for(int i = 0; i < n; i++) printf("%d ", A[i]);
    printf("\n");
  } else for(int i = 1; i <= n; i++) { // 尝试在A[cur]中填各种整数i
    int ok = 1;
    for(int j = 0; j < cur; j++)
      if(A[j] == i) ok = 0; // 如果i已经在A[0]~A[cur-1]出现过，则不能再选
    if(ok) {
      A[cur] = i;
      print_permutation(n, A, cur+1); // 递归调用
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  print_permutation(n, A, 0); 
  return 0;
}

输入输出

生成可重集的排列

// 可重集的全排列
// Rujia Liu
#include<cstdio>
#include<algorithm>
using namespace std;

int P[100], A[100];

// 输出数组P中元素的全排列。数组P中可能有重复元素
void print_permutation(int n, int* P, int* A, int cur) {
  if(cur == n) {
    for(int i = 0; i < n; i++) printf("%d ", A[i]);
    printf("\n");
	// 只需检查P的第一个元素和所有“与前一个元素不相同”的元素
	// 特例：1 1 1
  } else for(int i = 0; i < n; i++) if(!i || P[i] != P[i-1]) {
    int c1 = 0, c2 = 0;
	// A[0]～A[cur-1]中P[i]的出现次数c1
    for(int j = 0; j < cur; j++) if(A[j] == P[i]) c1++;
	// P数组中P[i]的出现次数c2
    for(int 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 i, n;
  scanf("%d", &n);
  for(i = 0; i < n; i++)
    scanf("%d", &P[i]);
  sort(P, P+n);
  print_permutation(n, P, A, 0);
  return 0;
}

输入输出

STL next_permutation

// 可重集的全排列(next_permutation版)
// Rujia Liu
#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
  int n, p[10];
  scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &p[i]);
  sort(p, p+n); // 排序，得到p的最小排列
  do {
    for(int i = 0; i < n; i++) printf("%d ", p[i]); // 输出排列p
    printf("\n");
  } while(next_permutation(p, p+n)); // 求下一个排列
  return 0;
}

输入输出