C++ 字典排序原理与实现

╰+攻爆jí腚メ 2022-08-02 00:18 194阅读 0赞

【摘要】

本文拟首先给出字典序的定义，字典序的物理含义；然后，介绍字典序的代码实现思想；最终，给出字典序的代码实现。

【正文】

**字典序的定义**

> n个元素\{1，2，...， n \}有n！个不同的排列。将这n！个排列按字典序排列，并编号为0，1，…，n！- 1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：
> 
> 字典序值 0 1 2 3 4 5
> 
> 排 列 123 132 213 231 312 321

**物理含义**

> 6个数字从左到右依次增大的。

**字典序的实现**

> 字典序法是由当前序列直接生成下一个排列的算法：排列定义：P = P1，P2，...，Pn
> 
> 第一步：求满足关系式P(k-1)<P(k)的k的最大值，设为i，即
> 
> i = max\{k|P(k-1)<P(k)\}
> 
> 第二步：求满足关系式P(i-1)<P(k)的k的最大值，设为j，即
> 
> j = max\{k|P(i-1)<P(k)\}
> 
> 第三步：P(i-1)与P(j)互换。
> 
> 第四步：把序列中P(i)P(i+1)\`\`\`P(n)顺序逆转。

**字典序的实例**

> 对于3421，可知 i = 2，j = 2 。P(1)与P(2)交换得4321，再将321逆转可得下一个排列4123 ；

**编程任务**

> 给定n 以及n个元素\{1，2，...，n\}的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
> 
>   
>

**代码实现**

#include<iostream>  
    #include<cmath>  
    using namespace std;  
    int main()  
    {  
        int n,i,j,Min,k,t;  
        int a[13];  
        __int64 sum;  
        int b[14];  
        int c[13];  
      
        freopen("in.txt","r",stdin);  
      
        sum=1;  
        for(i=1;i<=13;i++)  
        {  
            sum*=i;  
            b[i]=sum;  
        }  
        while(scanf("%d",&n)!=EOF)  
        {  
            for(i=0;i<n;i++)  
            {  
                scanf("%d",&a[i]);  
                c[i]=a[i]-1;  
            }  
            for(i=1;i<n;i++)  
                for(j=0;j<=i;j++)  
                {  
                    if(a[j]<a[i])c[i]--;  
                }  
            sum=0;b[0]=1;  
            for(i=0;i<n-1;i++)  
            {  
                sum+=c[i]*b[n-i-1];  
                //printf("%d ",c[i]);  
            }  
            //printf("/n");  
            t=-1;  
            for(i=n-1;i>=1;i--)  
                if(a[i-1]<a[i])  
                {  
                    t=i-1;  
                    break;  
                }  
            Min=14;  
            for(j=t+1;j<n;j++)  
                if(Min>a[j]&&a[j]>a[t])  
                {  
                    Min=a[j];  
                    k=j;  
                }  
            if(t!=-1)  
               swap(a[t],a[k]);  
            i=t+1;  
            j=n-1;  
            while(i<j)  
            {  
                swap(a[i++],a[j--]);  
            }  
            printf("%I64d/n",sum);  
            for(i=0;i<n;i++)  
                printf(i!=n-1?"%d ":"%d/n",a[i]);  
        }  
        return 0;  
    }

>   
>