Генерация лексикографических перестановок: ошибка сегментации

Question

Генерация лексикографических перестановок: ошибка сегментации

У меня есть этот код для создания лексикографических перестановок. Используется следующая логика:

Начните с возрастания порядка расположения символов в заданной тестовой строке.
Для генерации следующей лексикографической перестановки:

а) найти самый правый символ, который меньше, чем его следующий символ. Скажи А.

б) справа от А, найти следующий больший символ. Скажите Б. и поменяйте местами А & B.

в) справа от исходной позиции А, сортируйте символы в порядке возрастания.

Алгоритм заканчивается, когда мы получаем последнюю перестановку. т. е. обратное задание тестовой строки.
моя тестовая строка s = "0123456789"

Редактировать:
При каждом запуске программы я получаю отдельную позицию ошибки сегментации.

чтобы получить:

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" тогда я получаю ошибки сегментации.
Пожалуйста помоги!!

2

c++lexicographic permutation segmentation-fault

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я подозреваю, что ваш размер стека пересекает свой предел. Если вы работаете в Linux, сделайте «limit» и посмотрите свой размер стека. Есть два способа избежать этой ситуации

1) (Не рекомендуется) Делать «ограничение размера стека неограниченным» (только если вы работаете в системе на основе 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», и, следовательно, ваш предел размера не будет превышен

1