| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 6229 | Accepted: 3737 |
Description
abaabc
abaacb
ababac
Input
Output
Sample Input
abaacb cbbaa #
Sample Output
ababac No Successor
Source
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
char s[100];
int len;
bool get()
{
len=strlen(s);
int i=len-1;
while(i>0 && s[i-1]>=s[i] )
i--; //找到最后一个正序
if(i==0)
return false; //表示当前排列为最后一个排列，则返回false
int pos=i;
for(int j=i+1; j<len; j++)
{
if(s[j]<=s[i-1] )
continue;
if(s[j] < s[pos] )
pos=j;
}
swap(s[pos], s[i-1]);
sort(s+i, s+len);
return true;
}
int main()
{
//判断一个序列还有没有下一个全排列序列 如果存在就输出
while(scanf("%s", s)!=EOF )
{
if(s[0]==‘#‘) break;
if( get()==true )
printf("%s\n", s);
else
printf("No Successor\n");
}
return 0;
}
分析：利用该算法，也可以一直输出下去，从串的当前字典位置开始，直到输出至最后一个字典序。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
char s[100];
int len;
bool get()
{
len=strlen(s);
int i=len-1;
while(i>0 && s[i-1]>=s[i] )
i--; //找到最后一个正序
if(i==0)
return false; //表示当前排列为最后一个排列，则返回false
int pos=i;
for(int j=i+1; j<len; j++)
{
if(s[j]<=s[i-1] )
continue;
if(s[j] < s[pos] )
pos=j;
}
swap(s[pos], s[i-1]);
sort(s+i, s+len);
return true;
}
int main()
{
//判断一个序列还有没有下一个全排列序列 如果存在就输出
while(scanf("%s", s)!=EOF )
{
if(s[0]==‘#‘) break;
if(get()==true){
printf("%s\n", s);
while( get()==true )
printf("%s\n", s);
}
else
printf("No Successor\n");
}
return 0;
}
还可以这样变体：将初始输入的字符串进行排序：然后在利用上面的代码，输出当前串的所有排列
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
char s[100];
int len;
bool get()
{
int i=len-1;
while(i>0 && s[i-1]>=s[i] )
i--; //找到最后一个正序
if(i==0)
return false; //表示当前排列为最后一个排列，则返回false
int pos=i;
for(int j=i+1; j<len; j++)
{
if(s[j]<=s[i-1] )
continue;
if(s[j] < s[pos] )
pos=j;
}
swap(s[pos], s[i-1]);
sort(s+i, s+len);
return true;
}
int main()
{
//判断一个序列还有没有下一个全排列序列 如果存在就输出
while(scanf("%s", s)!=EOF )
{
if(s[0]==‘#‘) break;
len=strlen(s);
sort(s, s+len);
printf("%s\n", s);
if(get()==true){
printf("%s\n", s);
while( get()==true )
printf("%s\n", s);
}
else
printf("No Successor\n");
}
return 0;
}
poj 1146 ID Codes (字符串处理 生成排列组合 生成当前串的下一个字典序排列 【*模板】 )
原文：http://www.cnblogs.com/yspworld/p/4363900.html