紫书之枚举排列

简介: 紫书之枚举排列

1.生成1–n的排列


思路:先输出1开头的排列(这一步是递归调用),然后输出以2开头二点排列(也是递归调用),接着以3开头的排列,…最后以n开头的排列.

递归函数需要一下参数:

已经确定的前缀序列,以便输出

需要进行全排列的元素集合,以便依此选做第一个元素。

void print_permutation(序列A, 集合S) {
    if(S.empty()) 输出A;
    else {按照从小到大的顺序依此考虑S的每个元素v
        print_permutation(在A的末尾加v后得到的新序列, S-{v});
    }

实现代码:

#include<iostream>
#include<cstdio>
using namespace std;
int A[101];//用于存放全排列后的元素 
//输出1---n的 全排列
//n:全排列元素的结束位置,cur:当前A序列元素的个数.
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++){//枚举所有的可能i 
      int ok = 1;
      for(int j = 0; j < cur; j++){//判断 i是否已经在 序列A 中出现过了. 
        if(A[j]==i){
          ok = 0;//进行标记 
        }
      }
      if(ok){//如果没有出现过,就把i放到A序列的最后一个位置处. 
        A[cur] = i;
        print_permutation(n,A,cur+1);//继续进行递归调用. 将元素加入A序列. 
      }     
    }
  } 
} 
int main()
{
  int n;
  scanf("%d",&n);
  print_permutation(n,A,0);
  return 0;
 } 

运行结果:

20210614171244544.png

2.生成可重复的排列

问题描述:输入数组P,并按照字典序输出数组A各元素的所有全排列.

P里面的元素可能会有重复的,所有处理时有很多注意点.

对于重复元素,后序该加多少个.如何进行处理

在寻找下一个元素时对于重复元素如何处理.

#include<cstdio>
#include<algorithm>
using namespace std;
int P[100],A[100];
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 = 0;i<n;i++){//枚举每一个元素   这里的if是为了排除同一位置重复搞的情况. 不然会出现重复的情况   如:先把第一个1作为开头,再把第二个1作为开头,再把第三个1,作为开头,这样就会导致重复. 
      if(!i||P[i]!=P[i-1]){//==>>去除重复的元素.   由于P数组已经进行过排序了,  在处理时,
                //当当前元素和前面的元素一致,此种情况便不再进行枚举.
        int c1 = 0,c2 = 0;//c1,c2的使用是因为 P中会有重复的,所以构成的序列也有多个重复元素. 当 < 时,才进行加入.. 
        for(int j = 0; j<cur;j++){//统计当前元素在A中的个数. 
          if(A[j]==P[i]){
            c1++;
          }
        }
        for(int j = 0; j < n; j++){//统计当前元素在P中的个数. 
          if(P[i]==P[j]){
            c2++;
          }
        }
        if(c1 < c2){//如果A中的该元素 < P中的该元素,则直接加入A.  因为P中会有重复的,所以构成的序列也有多个重复元素. 
          A[cur] = P[i];
          print_permutation(n,P,A,cur+1);//继续递归. 
        }
      }
    }
  } 
}
int main()
{
  int n;
  scanf("%d",&n);
  for(int i = 0;i<n;i++){
    scanf("%d",&P[i]);
  }
  sort(P,P+n);
  print_permutation(n,P,A,0);
  return 0;
}

运行结果:

20210614174636508.png

3.STL之求下一个序列

STL 为我们提供了next_permutation(),这个可以方便的求枚举排列.

#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);  
  do{//这个一般和do...while进行搭配使用. 
    for(int i = 0;i < n;i++){
      printf("%d",p[i]);//输出 
    }
    printf("\n"); 
  }while(next_permutation(p,p+n));
  return 0;
 } 

运行结果:

20210614175551649.png

注:STL还有一个prev_permutaion()可以求上一个序列。

总结:枚举排列的方法有两种:一是递归枚举,二是用STL中的next_permutation().

相关文章
|
5月前
|
算法
现有‘abcdefghijkl’12个字符,将其所有的排列按字典序进行排序,给出任意一组排列,说出这租排列在所有排列中是第几小的
现有‘abcdefghijkl’12个字符,将其所有的排列按字典序进行排序,给出任意一组排列,说出这租排列在所有排列中是第几小的
45 1
|
11月前
递归实现排列型枚举
递归实现排列型枚举
|
11月前
|
算法 程序员 C#
C++二分查找算法:132 模式枚举3
C++二分查找算法:132 模式枚举3
|
C++
C++ leetcode之排列与组合专题
C++ leetcode之排列与组合专题
84 0
sort如果按字典序排列的细节
sort如果按字典序排列的细节
80 0
|
机器学习/深度学习
排列型枚举底层讲解(两种解法)
排列型枚举底层讲解(两种解法)
排列型枚举底层讲解(两种解法)
20天刷题计划-567. 字符串的排列
二、思路分析: 判断 s2 中判断是否包含 s1 的排列, 而子串必须是连续的,所以要求的 s2 子串的长度跟 s1 长度必须相等。。这道题主要用到思路是:滑动窗口. 创建两个数组, 数组一存放字符串一中各字母的个数,数组二存放字符串2中各字母的个数; 开始时,先将两数组中前n个(n是字符串1的长度)字符数目,加入到两个数组中,判断是否相等; 若不包含子串排列,则窗口右移一格,数组2中的字母个数随之变化; 初始化取得第一个滑动窗口的目标值 继续滑动窗口,每往前滑动一次,需要删除一个和添加一个元素
|
机器学习/深度学习
【组合数学】排列组合 ( 两个计数原则、集合排列示例 | 集合排列、圆排列示例 )
【组合数学】排列组合 ( 两个计数原则、集合排列示例 | 集合排列、圆排列示例 )
216 0