枚举排列各算法

  1. 生成1~n的全排列
    • 数组版
      cpp
      // c语言数组版
      // n是全排列的数字个数,也是数组A的最大长度,cur表示已经填充的数字个数
      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; // 表示当前待填充的整数i是否已经有过,填充进去是否ok
      for (int j = 0; j < cur; j++){ // 在填充过的数字中找数字i
      if (A[j] == i) {
      ok = 0; // 出现过就不能填这个数字了,就不ok
      break;
      }
      }
      if (ok){
      A[cur] = i; // 如果能填的话就填进去
      print_permutation(n, A, cur + 1); // 然后递归调用下一位
      }
      }
      }
      // 调用方式
      print_permutation(n, A, 0); // 开始填充个数为0
    • vector版
      cpp
      void print_permutation(vector<int>& A, int n){
      if (A.size() == n){
      for (auto num : A){
      cout << num << ' ';
      }
      cout << endl;
      }
      else for (int i = 1; i <= n; i++){
      bool ok = true;
      for (auto num : A){
      if (num == i){
      ok = false;
      break;
      }
      }
      if (ok){
      A.push_back(i);
      print_permutation(A, n);
      A.pop_back(i);
      }
      }
      }
      // 调用方式
      print_permutation(A, n);
  2. 生成可重集的排列。输入数组P,并按字典充输出数组P中各元素的所有全排列,数组A是缓存数组。数组P中允许有重复元素
    • 数组版
      cpp
      // c语言数组版
      // n是全排列的数字个数,即数组P的长度,也是数组A的最大长度,cur表示已经填充的数字个数
      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");
      }
      else for (int i = 1; i <= n; i++){ // 尝试在A[cur]中填各种整数P[i]
      if (i == 0 || P[i] != p[i - 1]){ // 不能连续枚举重复的整数P[i]
      int c1 = 0, c2 = 0; // c1表示A中P[i]出现的次数,c2表示P中P[i]出现的次数
      for (int j = 0; j < cur; j++){
      if (A[j] == P[i]) c1++;
      }
      for (int j = 0; j < n; j++){
      if (P[j] == P[i]) c2++;
      }
      if (c1 < c2){
      // 只要重复次数没达到上限,就可以继续重复
      A[cur] = P[i]; // 如果能填的话就填进去
      print_permutation(n, P, A, cur + 1); // 然后递归调用下一位
      }
      }
      }
      }
      // 调用方式
      print_permutation(n, P, A, 0); // 开始填充个数为0
    • vector版
      cpp
      void print_permutation(vector<int>& A, vector<int>& P){
      if (A.size() == P.size()){
      for (auto num : A){
      cout << num << ' ';
      }
      cout << endl;
      }
      else for (int i = 0; i < P.size(); i++){
      if (i == 0 || P[i] != P[i - 1]){
      int c1 = 0, c2 = 0;
      for (auto num : A){
      if (num == P[i]) c1++;
      }
      for (auto num : P){
      if (num == P[i]) c2++;
      }
      if (c1 < c2){
      A.push_back(P[i]);
      print_permutation(A, P);
      A.pop_back();
      }
      }
      }
      }
      // 调用方式
      print_permutation(A, P);
  3. 下一个排列
    cpp
    // 使用STL的库函数next_permutation
    int p[10];
    vector<int> q; // 其中均存储有某种排列
    next_permutation(p, p + 10);
    next_permutation(q.begin(), q.end()); // 均为获得下一排列
    // 调用成功(存在下一排列时)返回true,失败返回false

发表评论