排列的字典序问题
1．问题描述：
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
2．编程任务：
给定n 以及n 个元素{1,2,?, n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
3．数据输入：
由文件input.txt提供输入数据。文件的第1 行是元素个数n。接下来的1 行是n个元素{1,2,..., n }的一个排列。
4．结果输出：
程序运行结束时，将计算出的排列的字典序值和按字典序排列的下一个排列输出到文件output.txt中。文件的第一行是字典序值，第2行是按字典序排列的下一个排列。
输入文件示例 输出文件示例
input.txt output.txt
8 8227
2 6 4 5 8 1 7 3 2 6 4 5 8 3 1 7

[此贴子已经被作者于2007-11-7 19:35:30编辑过]

占个沙发.
以备后用.

/*程序已解决,过几天发上来,大家参考下.*/

[此贴子已经被作者于2007-11-7 19:36:52编辑过]

c++ stl 中next_permutation就是产生的字典序排列


自己要写可以看这个
http://blog.bc-cn.net/user20/130988/archives/2007/6553.shtml

用递归能产生排列，但是要保证字典序比较多花些工夫，可以想想。

//请先在此目录下建一个名为qingsongin.txt的文件,里面内容为:
//8
//2 6 4 5 8 1 7 3


#include<iostream>
#include<fstream>
using namespace std;
int fac(int n)
{
  if(n==0||n==1)
      return 1;
      else
      return fac(n-1)*n;
}//计算阶乘

void Swap(int *i,int *j)
{
    int t;
    t=*i;
    *i=*j;
    *j=t;
}
int permRank(int n,int *a ,int &r,int *rho)
{
    //int rho[100];
  r=0;
  for(int j=1;j<=n;j++) rho[j]=a[j];
  for(j=1;j<=n;j++)
  {
    r+=(rho[j]-1)*fac(n-j);
    for(int i=j+1;i<=n;i++)
    if(rho[i]>rho[j]) rho[i]--;
  }
  //for(int i=1;i<=n;i++)
    //cout<<rho[i]<<" ";
  return r;
}//计算序值


void permUnrank(int n,int r,int *rho)
{
    rho[n]=1;
    for(int j=1;j<n;j++)
    {
        int d=(r%fac(j+1))/fac(j);
    r-=d*fac(j);
    rho[n-j]=d+1;
    for(int i=n-j+1;i<=n;i++)
        if(rho[i]>d) rho[i]++;
    }
    //for(int i=1;i<=n;i++)
//    cout<<rho[i]<<" f";
}//由字典序值计算排列,并由数组rho返回

void permSucc(int n,int *pi,int *p)
{
  pi[0]=0;
  int i=n-1;
  while(pi[i+1]<pi[i])
  {i--;}
    if(i==0)  cout<<"ERROR"<<endl;//flag=0;
  else//flag=1;
  {
      int j=n;
  while(pi[j]<pi[i])
      j--;
  int *k,*l;
  k=&pi[i];
  l=&pi[j];
    //Swap(pi[i],pi[j]);
  Swap(k,l);
          //int t=pi[i];
        //pi[i]=pi[j];
        //pi[j]=t;
      for(int h=i+1;h<=n;h++) p[h]=pi[h];
      for(h=i+1;h<=n;h++) pi[h]=p[n+i+1-h];      
  }

}

int main()
{
    int i,n,r;
    int a[100];
    int pi[100];
    int p[100];
    int rho[100];

    ifstream fin("qingsongin.txt");
    ofstream fout("qingsongout.txt");

    if (fin.fail())
    {
        cout<<"qingsongin.txt文件输入出错!"<<endl;
        return 1;
    }

    if (fout.fail())
    {
        cout<<"qingsongout.txt文件输出出错!"<<endl;
        return 2;
    }


    //cout<<"请输入数组的长度："<<endl;
    fin>>n;
    //cout<<"请输入元素:"<<endl;
    for(i=1;i<=n;i++)
        fin>>a[i];
        permRank(n,a,r,rho);
    //cout<<"此排列的字典序值是: "<<endl;
    fout<<"此排列的字典序值是: "<<endl;
    //cout<<r<<endl;
    fout<<r<<endl;
    permUnrank(n,r,rho);
    cout<<"请选择计算下一序列的方法:"<<endl;
    cout<<"1.方法一(序列值加一)"<<endl;
    cout<<"2.方法二(通过原序列)"<<endl;
    int x;
    cin>>x;
    switch(x)
    {
    case 1:
        {
                permUnrank(n,r+1,rho);//r+1既下一排列
                //cout<<"方法一计算出的下一排列是:"<<endl;
                //for(i=1;i<=n;i++)
                //cout<<rho[i]<<" ";//计算前的排列
                //cout<<endl;
                fout<<"方法一计算出的下一排列是:"<<endl;
                for(i=1;i<=n;i++)
                fout<<rho[i]<<" ";//计算前的排列
                fout<<endl;
                break;
        }
    case 2:
        {
                permSucc(n,rho,pi);
                //cout<<"方法二计算出的下一个排列是:"<<endl;
                fout<<"方法二计算出的下一个排列是:"<<endl;
                for(i=1;i<=n;i++)
                //cout<<rho[i]<<" ";//计算出的下一个排列
                //cout<<endl;
                fout<<rho[i]<<" ";//计算出的下一个排列
                fout<<endl;
                break;
        }
    default:
        cout<<"输入错误!没计算出下一排列!"<<endl;
        break;
    }
    cout<<"程序成功运行!"<<endl;
    cout<<"请查看此目录下的qingsongout.txt!"<<endl;
    return 0;
}