字典序問題演算法
① 字典序排序
實現獲取下一個排列的函數，演算法需要將給定數字序列重新排列成字典序中下一個更大的排列。
如果不存在下一個更大的排列，則將數字重新排列成最小的排列（即升序排列）。
必須原地修改，只允許使用額外常數空間。
以下是一些例子，輸入位於左側列，其相應輸出位於右側列。
示例：
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節講了