字典序问题算法
① 字典序排序
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
示例：
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解题思路：
怎么解呢？
方法一：暴力法
在这种方法中，我们找出由给定数组的元素形成的列表的每个可能的排列，并找出比给定的排列更大的排列。
但是这个方法是一种非常天真的方法，因为它要求我们找出所有可能的排列
因此，这种方法根本无法通过。 所以，我们直接采用正确的方法。
复杂度分析
时间复杂度：O(n!)，可能的排列总计有 n! 个。
空间复杂度：O(n)，因为数组将用于存储排列。
方法二：一遍扫描
首先，我们观察到对于任何给定序列的降序，没有可能的下一个更大的排列。
例如，以下数组不可能有下一个排列：
[9, 5, 4, 3, 1]
此题的目的是求一组元素可以组成的所有数字中比这组元素组成的数字下一大的一组序列
1.一种特殊情况：当序列的元素递减的时候肯定是不存在比它大的序列了，像[3,2,1]组成的数字321已经是最大的了
2.当不是上面的特殊情况的时候，举个例子：
[1,3,2,4]的下一大序列是[1,3,4,2]
[1,3,4,2]的下一大序列是[1,4,2,3]
[1,4,3,2]的下一大序列是[2,1,3,4]
所以我们要从上面找到规律
从上面，我们可以发现规律，从序列的后面向前面看，如果nums[i]>nums[i-1]那么这个序列就存在下一大元素
a.当序列的最后两个元素满足nums[i]>nums[i-1],那么直接交换位置就可以了，像[1,3,2,4]-->[1,3,4,2]
b.当序列是最后两个元素之前的元素满足nums[i]>nums[i-1]，那么我们就要考虑几个问题了，像[1,3,4,2]-->[1,4,2,3]
c.在[1,3,4,2]中，从后向前遍历，3和4满足条件，交换他们之后还要对i和之后元素进行排序，不然得到的就是[1,4,3,2]
d.在[1,4,3,2]中，1和4满足条件，但是我们不能直接交换他们，我们要在i之后的序列中找一个满足大于i-1位置元素的最小元素和它交换位置
② ACM 算法超难题目
出题人的表达能力太差，题目叙述得很糟糕，最后两个例子也错了
比较好的叙述是，输入n，输出从0到32中取6项按字典序排序下的第n个组合（从第0个组合0,1,2,3,4,5开始计）
这种谈不上什么难题，只不过是入门级的问题
在给定前k项的（记第k项为m）情况下余下的项共有C(32-m,6-k)种情况，这里C(x,y)表示x取y的组合数，以此编程即可
给你一个例子
#include<stdio.h>
intbinom(intn,intm)
{
inti,c=1;
if(2*m>n)
n=n-m;
for(i=1;i<=m;i++)
c=c*(n+1-i)/i;
returnc;
}
intmain()
{
inti,n;
intA[6]={-1};
while(scanf("%d",&n)!=EOF)
{
n++;
if(n<=0||n>binom(33,6))
{
printf("Invalidinput ");
continue;
}
for(i=1;i<=5;i++)
{
for(A[i]=A[i-1]+1;;A[i]++)
{
intt=binom(32-A[i],6-i);
if(n>t)
n-=t;
else
break;
}
printf("%d,",A[i]);
}
printf("%d ",A[i-1]+n);
}
return0;
}
③ 我的字典序全排列java程序，怎么改成非递归算法
packageLianxi.yong2;
importjava.util.LinkedList;
importjava.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[]args){
Aa=newA();
}
}
classA{
Scannercin=newScanner(System.in);
intn;
chara[];
publicA(){
n=cin.nextInt();
a=newchar[n];
for(inti=0;i<n;i++){
a[i]=(char)(i+49);
}
next();
}
privatevoidnext(){
//TODOAuto-generatedmethodstub
for(chari:a){
System.out.print(i+"");
}
System.out.println();
LinkedList<Integer>is=newLinkedList<Integer>();
LinkedList<Integer>js=newLinkedList<Integer>();
is.add(n-1);
js.add(n-1);
//假设我们不模拟递归的情况，就模拟多重循环(这比较简单，先做简单的事情)
//但是事实就是其实只要模拟一个多重循环就可以把问题解决了
while(!is.isEmpty()&&is.getLast()>0){
while(!js.isEmpty()&&js.getLast()>=is.getLast()){
intj=js.getLast();
inti=is.getLast();
js.removeLast();
js.addLast(j-1);
if(a[j]>a[i-1]){
swap(j,i-1);
xu(i);
for(charc:a){
System.out.print(c+"");
}
System.out.println();
is.add(n-1);
js.add(n-1);
}
}
js.removeLast();
js.addLast(n-1);
is.addLast(is.removeLast()-1);
}
}
privatevoidxu(inti){
//TODOAuto-generatedmethodstub
intj=n-1;
for(inti2=0;i+i2<j-i2;i2++){
if(i+i2<j-i2)
swap(i+i2,j-i2);
}
}
privatevoidswap(inti,intj){
//TODOAuto-generatedmethodstub
chartemp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
我不知道你的算法是否正确，但是如果8 9的话是得不到正确的结果的，不过我改写的竟然可以得到正确的结果，真是奇怪
④ 算法 字典序问题
#include<stdio.h>
#include<string.h>
const int N = 10;
int ans[N]; //ans[i]存放数字i出现的次数
char str[N]; //输入的数字
int a[N],len; //a[i]为10^i，len为数字的长度
void solve(long n) //统计数字n
{
long m=n+1;
memset(ans,0,sizeof(ans));
int j,i;
for(i=0;i<len;i++)
{
int x=str[i]-'0';
int t=(m-1)/a[len-i-1];
ans[x]+=m-t*a[len-i-1];//自左往右到i位数字不变条件下，i位为x的数字个数
t=t/10;
j=0;
while(j<x)
{
ans[j]+=(t+1)*a[len-i-1];//统计当前位置为j出现的个数
j++;
}
while(j<N) //统计当前位置为j的数目
{
ans[j]+=t*a[len-i-1];
j++;
}
ans[0]-=a[len-i-1];//消去前导0
}
for(i=0;i<N;i++)
printf("%d\n",ans[i]);
}
int main()
{
int i;
a[0]=1;
for(i=1;i<N;i++)
a[i]=a[i-1]*10;
long n;
while(scanf("%s",str)!=EOF)
{
n=0;
len=strlen(str);
for(int i=0;i<len;i++)
n=n*10+str[i]-'0';
solve(n);
}
return 0;
}
⑤ 将整数按字典序排序的算法（我不是要一段程序或者一个例子，是想知道这种算法的思路是啥），谢谢
同样一组整数，分别用二进制表示和十进制表示，它们的字典顺序也会不一样，因此我认为还是得先把整数转换成相应的进制表示法的字符串形式，如把 123 和 23 转换成 "123" 和 "23"，然后从首字符开始逐一比较，得到字典顺序
⑥ 字典序的算法说明
设置了中介数的字典序全排列生成算法，与递归直接模拟法和循环直接模拟法的最大不同是，不需要模拟有序全排列的生成过程，也就不需要逐一地生成各个全排列，只要知道初始全排列，就能根据序号（m-1），直接得到第m个全排列，因此速度非常快。它的缺点是在生成序号（m-1）的递增进进制数时，需要事先创建一个用来存储n的阶乘数n! 的数组p[]，所以n的值不能太大，否则就会溢出，根据我的测试结果，当1<=n<=20时不会溢出，当21<=n时会溢出。
设置了中介数的字典序全排列生成算法需要设置中介数，在实际应用中比较繁琐，不如由前一个排列直接推得下一个排列方便。
⑦ 求一个c语言按字典序全排列的方法
如果是想学习一下算法，用c语言不错。如果是实际使用需要，就用现成的木头超级字典生成器(MutouDic)，工具集里有一个排列字典工具，可以生成任意个元素，任意长度的升序排列、降序排列和全排列。
⑧ 关于全排列的算法问题
最低0.27元/天开通网络文库会员，可在文库查看完整内容>
原发布者:ON9V4Xr2gU9J7
全排列以及相关算法在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C++。本文的节数：1.全排列的定义和公式：2.时间复杂度：3.列出全排列的初始思想：4.从第m个元素到第n个元素的全排列的算法：5.全排列算法：6.全排列的字典序：7.求下一个字典序排列算法：8.C++STL库中的next_permutation()函数：（#include）9.字典序的中介数，由中介数求序号：10.由中介数求排列：11.递增进位制数法：12.递减进位制数法：13.邻位对换法：14.邻位对换法全排列：15.邻位对换法的下一个排列：16.邻位对换法的中介数：17.组合数的字典序与生成：由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法，仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数，仅供参考。第17节讲了