全排列生成算法之字典序-白红宇

全排列生成算法之字典序

阅读量：4156 次

发布时间：2019-05-25

本文共 974 字，大约阅读时间需要 3 分钟。

算法描述的参考链接：

使用字典序输出全排列的思路是，首先输出字典序最小的排列，然后输出字典序次小的排列，……，最后输出字典序最大的排列。这里就涉及到一个问题，对于一个已知排列，如何求出其字典序中的下一个排列。

这里给出算法步骤：

对于排列a[1...n]，找到所有满足a[j]<a[j+1](0<j<n-1)的j的最大值，即为i。如果这样的i不存在，则说明当前排列已经是a的所有排列中字典序最大者，所有排列输出完毕。a[i+1]...a[n]为降序排列的。

在a[i+1...n]中，寻找满足这样条件的元素k，使得在所有a[k]>a[i]的元素中，a[k]取得最小值。也就是说a[i]<a[k]，a[i]>a[k+1]。

交换a[i]与a[k].

对于a[i+1...n]，反转该区间内元素的顺序。也就是说a[i+1]与a[n]交换，a[i+2]与a[n-1]交换，……，这样就得到了a[1...n]在字典序中的下一个排列。

如何得到21453

1.从尾部找第一个a[i]<a[i+1]的位置

找到4

2.从4往后找到最后一个大于4的数5

3.交换4和5，变为21543

4.反转5后面区间内的元素，21534

附上我的代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=15;int a[2][maxn];int flag=0;int n,cnt;void init() {    cnt=1;    printf("the full permutation of %d is\n",n);    for(int i=0; i
       
        =1; j--) {                if(a[flag][j-1]
        
         a[flag][j]) { k=j-1; break; } } tmp=a[flag][i]; a[flag][i]=a[flag][k]; a[flag][k]=tmp; for(int j=0; j<=i; j++) { a[!flag][j]=a[flag][j]; } for(int j=i+1; j

转载地址：http://clwxi.baihongyu.com/

你可能感兴趣的文章