排列的字典序问题

排列的字典序问题

时间: 1ms        内存:64M

描述:

n个元素{1,2,……, n }有n!个不同的排列。将这n!个排列按字典序排列,并编号为0,1,…,n!-1。每个排列的编号为其字典序值。例如,当n=3时,6 个不同排列的字典序值如下:

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

输入:

输入数据的第1行是元素个数n(n≤20)。接下来的1行是n个元素 {1,2,……, n }的一个排列。

输出:

输出数据的第1行是字典序值,第2行是按字典序排列的下一个排列。

示例输入:

8
2 6 4 5 8 1 7 3

示例输出:

8227
2 6 4 5 8 3 1 7

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<stdlib.h>
void SWAP(int * a, int * b)
{
    long long t;
    t = *a;
    *a = *b;
    *b = t;
}
int main()
{
    int n,i,k,j,t,order[100];
    int lis,f[100],mid,h;
    f[0]=1;
    for(i=1;i<=22;i++)
        f[i]=f[i-1]*i;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&order[i]);
        if(n==1)    printf("0\n1\n");
        else if(n>=2)
        {
            lis=0;
            for(i=0,k=n-1;i<n-1;i++,k--)
            {
                t=0;
                for(j=0;j<i;j++)
                    if(order[j]<order[i])    t++;
                lis+=(order[i]-1-t)*f[k];
            }
            printf("%d\n",lis);

            for(i = n-2; i >= 0; i--)
            {
                if(order[i] < order[i+1])
                {
                    j = i;
                    for(k = n-1; k > j; k--)
                    {
                        if(order[k] > order[j])
                        {
                            mid = j+(n-j)/2;
                            SWAP(&order[j], &order[k]);
                            for(j++, h = 1; j <= mid; j++, h++)
                                SWAP(&order[j], &order[n-h]);
                        }
                    }
                    break;
                }
            }
            for(i=0; i < n-1; i++)
                printf("%d ",order[i]);
            printf("%d",order[i]);
        }
    }
    return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll f(ll n)
{
    if(n==1)return 1;
    return n*f(n-1);
}
int get_th(int s[],int n)  // 数组中第一个数在所有数里排第几   最小是0
{
    int x=0;
    for(int i=1;i<n;i++)
    {
        if(s[i]>s[0])x++;
    }
    return n-x-1;
}
bool dj(int s[],int n)
{
    for(int i=1;i<n;i++)
    {
        if(s[i]>s[i-1])return false;
    }
    return true;
}
void sort1(int s[],int n)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(s[i]>s[j])
                swap(s[i],s[j]);
        }
    }
}
void swap_(int s[],int n)
{
	int key=s[0];
	int min;
	bool first=true;
	for(int i=1;i<n;i++)
	{
		if(s[i]>key)
		{
			if(first)
			{
				first=false;
				min=i;
			}
			else
			{
				if(s[i]<s[min])min=i;
			}
		}
	}
	swap(s[0],s[min]);
}
int main()
{   
    int n;
    int i;
    cin>>n;
    int s[21];   // 排序完的顺序
    for(i=0;i<n;i++)
    {
       cin>>s[i];
    }
    ll num=0;
    for(i=0;i<n-1;i++)
    {
        int k=get_th(&s[i],n-i);
        num= num + k*f(n-i-1);
    }
    cout<<num<<endl;
    for(i=n-2;i>=0;i--)
    {
        if(dj(&s[i],n-i))continue;
		swap_(&s[i],n-i);
        sort1(&s[i+1],n-i-1);
        break;
    }
    for(i=0;i<n;i++)
        cout<<s[i]<<" ";
    cout<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注