排列的字典序问题
效云 李
n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下： 字典序值 0 1 2 3 4 5 排列 123
132 213 231 312 321 « 编程任务： 给定n 以及n 个元素{1,2, , n }的一个排列，计算出这个排列的字典序值，以
及按字 典序排列的下一个排列。 « 数据输入： 由文件input.txt提供输入数据。文件的第1 行是元素个数n。接下来的1 行是n个元素
{1,2, , n }的一个排列。 « 结果输出: 程序运行结束时，将计算出的排列的字典序值和按字典序排列的下一个排列输出到文件
output.txt中。文件的第一行是字典序值，第2行是按字典序排列的下一个排列。 输入文件示例 输出文件示例 input.txt
output.txt 8 2 6 4 5 8 1 7 3 8227 2 6 4 5 8 3 1 7
效云 李
// 递归分治-排列的字典序问题.cpp : Defines the entry point for the console
application.
//
#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n=0;
string s;
ifstream finput;
finput.open("input.txt");
finput>>n;
finput>>s;
finput.close();
int *v=new int[n+1];
int i=0;
for(i=1;i<=n;++i)
{
v[i]=s[i-1]-48;
}
int calculat_num(int*,int);
int (*p_calculat_num)(int*,int);
p_calculat_num=calculat_num;
int num=(*p_calculat_num)(v,n);
void next_num(int*,int);
void (*p_next_num)(int*,int);
p_next_num=next_num;
(*p_next_num)(v,n);
ofstream foutput;
foutput.open("output.txt");
foutput<<num<<endl;
for(i=1;i<=n;++i)
{
foutput<<v[i];
}
foutput.close();
delete [] v;
return 0;
}
void next_num(int* v,int n)
{
int max=n;
while(v[max]<v[max-1])
{
--max;
}
int i=max;
while(v[max-1]<v[i])
{
++i;
if(i==(n+1)) break;
}
int temp=v[max-1];
v[max-1]=v[i-1];
v[i-1]=temp;
int j=max;
while(j<n)
{
temp=v[n];
v[n]=v[j];
v[j]=temp;
++j;
--n;
}
}
int calculat_num(int* v,int n)
{
int *num=new int[n+1];
int result=0;
int factorial(int);
int (*p_factorial)(int);
p_factorial=factorial;
for(int i=1;i<=n;++i)
{
num[i]=0;
for(int j=i;j<=n;++j)
{
if(v[j]<v[i]) num[i]+=1;
}
}
for(int i=1;i<=n;++i)
{
result+=num[i]*(*p_factorial)(n-i);
}
delete [] num;
return result;
}
int factorial(int n)
{
if(n==0)return 0;
int result=1;
for(int i=1;i<=n;++i)
{
result*=i;
}
return result;
higer
************************************************************************/
/* 排列的字典序问题 */
/
************************************************************************/
#include "stdio.h"
#include <string.h>
#define NUM 10
int curr=0;
int factorial(int n){//计算阶乘
if(n==0) return 1;
else return n*factorial(n-1);
}
void sort(int* a,int n){//冒泡排序算法
int i=0,temp;
int j=n-1;
for(j=n-1;j>0;j--)
for (i=0;i<j;i++) {
if(a[i]>a[i+1]){
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
int index(int* a,int n,int* flag){//计算字典序值，从1开始的，输出时减1
int i=0,m=0;
for (i=1;i<=n;i++) {//可能的数字
if (i<a[curr]&&flag[i]==0) {
m++;
}
}
if(curr==n) return 1;//全部排完
else{
flag[a[curr]]=1;//排列一个
curr++;
return m*factorial(n-curr)+index(a,n,flag);
}
}
int next(int* a,int* b,int n){//求a的一下个排列b
int i=n-2;
int temp=a[n-1];
while(i>=0&&a[i]>temp){
temp=a[i];
i--;
}
if(i<0) return -1;//是递减排序的，已经是最后一个排列，所以下一个排列不存在
temp=a[i];//如果下一个排列存在
int j=0;
for (j=0;j<n;j++) b[j]=a[j];//复制
int *p=b+i;
sort(p,n-i);//对从该位置开始到最后的一部分排序
j=i;
while (b[j]!=temp) j++;//找到排序后的位置，一定不是最后一个
temp=b[j+1];//保存比它大的一个值
int k=j+1;
for(k=j+1;k>i;k--) b[k]=b[k-1];//移动
b[i]=temp;//恢复
return 0;
}
int main(){
int n;
scanf("%d",&n);
int a[NUM];
memset(a,0,sizeof(a));
int i=0;
for (i=0;i<n;i++) {
scanf("%d",&a[i]);
}
int flag[NUM];
memset(flag,0,sizeof(flag));
printf("%d\n",index(a,n,flag)-1);
int b[NUM];
memset(b,0,sizeof(b));
if(next(a,b,n)==-1) printf("它是最后一个排列，下一个排列不存在\n");
else{
for (i=0;i<n;i++) printf("%d ",b[i]);
printf("\n");
}
return 0;
}
总觉得这道题应该有更好的巧妙的方法......
higer
第一组：
1
8
第二组
2
2 1
第三组
8
8 7 6 5 4 3 2 1
看能不能通过某些边界条件。