我有这段代码可以生成字典排列。使用以下逻辑:
- 从给定测试字符串中字符的升序排列开始。
- 生成下一个字典排列:
a) 找到最右边比下一个字符小的字符。说 A.
b) 在 A 的右边,找到下一个更大的字符。说 B. 并交换 A 和 B。
c) 在A原位置的右边,按升序排列字符。
当我们得到最后一个排列时,算法结束。即给定测试字符串的反向。
我的测试字符串 s = "0123456789"
编辑: 在程序的每次运行中,我都会得到一个单独的段错误位置。
得到A:
int firstchar(string s){
int pos = s.length()-2;
for(int i=pos;i>=0;i--){
if(s[i]<s[i+1]){
pos = i;
break;
}
}
return pos;}
获取 B 然后递归方法(qsort 是 <cstdlib>
的一个函数):
int ceilchar(string s, int fc){
int ceil = fc+1;
int diff=27;
for(int i=ceil;i<s.length();i++){
if(s[i]>s[fc] && s[i]-s[fc]<diff){
ceil = i;
diff = s[i]-s[fc];
}
}
return ceil;}
启动函数:
void nextpermute(string& s){
int fc = firstchar(s);
int cc = ceilchar(s,fc);
swap(s,fc,cc);
sort(&s[fc]+1,&s[fc]+s.length()-fc);
if(s!="9876543210"){
cout<<s<<"\n";
nextpermute(s);
}
else
cout<<s<<"\n";}
从主调用:nextpermute(test);
如果测试字符串是 "01234567"
或任何比这更小的字符串,它就可以正常工作。但如果它是一个像这样的字符串
"012345678"
或 "0123456789"
,然后我得到段错误。
请帮忙!!
最佳答案
我怀疑您的筹码量超出了限制。如果您在 Linux 上运行它,请执行“限制”并查看您的堆栈大小。有两种方法可以避免这种情况
1)(不推荐)执行“limit stacksize unlimited”(仅当您在基于 unix 的系统上时)。并再次运行该程序。
2)(推荐)。
改变
void nextpermute(string& s){
int fc = firstchar(s);
int cc = ceilchar(s,fc);
swap(s,fc,cc);
sort(&s[fc]+1,&s[fc]+s.length()-fc);
if(s!="9876543210"){
cout<<s<<"\n";
nextpermute(s);
}
else
cout<<s<<"\n";
}
到
void nextpermute(string& s){
int fc = firstchar(s);
int cc = ceilchar(s,fc);
swap(s,fc,cc);
sort(&s[fc]+1,&s[fc]+s.length()-fc);
cout <<s<<"\n";
}
并将您的主要功能修改为
int main()
{
string s = "0123456789";
while (s != "9876543210")
{
nextpermute(s);
}
}
以上更改将取消“nextpermute”的递归,因此您的堆栈大小限制将永远不会被超过
关于c++ - 生成字典排列 : Segmentation fault,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18160250/