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

【摘要】

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

【正文】

字典序的定义

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;
}

最后

以上就是高贵盼望为你收集整理的C++ 字典排序 原理与实现的全部内容，希望文章能够帮你解决C++ 字典排序 原理与实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。