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

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

  1. Начните с расположения символов в порядке возрастания в заданной тестовой строке.
  2. Чтобы сгенерировать следующую лексикографическую перестановку:

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

б) справа от A найти следующий больший символ. СКАЖИТЕ Б. и поменяйте местами А и Б.

в) справа от исходной позиции A отсортировать символы по возрастанию.

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


person activatedgeek    schedule 10.08.2013    source источник
comment
Что не так с std::next_permutation?   -  person chris    schedule 10.08.2013
comment
@chris, я пытаюсь решить это сам. один раз, конечно, я бы использовал это   -  person activatedgeek    schedule 10.08.2013
comment
И почему вы используете strcmp с s.c_str() вместо operator== с s? Вам удалось взять безопасный код и сделать его небезопасным.   -  person chris    schedule 10.08.2013
comment
о да! просто вылетело из головы, я могу напрямую сравнивать строковые объекты. в любом случае, это все еще не решает мою проблему.   -  person activatedgeek    schedule 10.08.2013
comment
Если вы получаете seg-fault, вы должны запустить свой код в отладчике, чтобы определить, какая строка вызывает проблему. Затем работайте в обратном направлении оттуда.   -  person Oliver Charlesworth    schedule 10.08.2013
comment
почему гибридный стиль C/C++? вместо qsort, strlen и strcmp используйте std::sort и функции-члены std::string   -  person TemplateRex    schedule 10.08.2013
comment
@activatedGeek Еще одно исправление: используйте std::sort() форму <algorithm> вместо qsort().   -  person    schedule 10.08.2013
comment
да, я напечатал отладку. данные: я заметил, что эта ошибка возникает около 87300-го вызова функции ceilchar(string&); и в каждом прогоне это число разное, но только около этого. если я использую вывод, предположим, 87319-го вызова и начинаю оттуда, он работает вперед, но снова при каком-то 176000-м вызове снова ошибка сегментации!   -  person activatedgeek    schedule 10.08.2013
comment
@H2CO3 конечно! но до сих пор не исправить!   -  person activatedgeek    schedule 10.08.2013


Ответы (1)


Я подозреваю, что размер вашего стека превышает свой предел. Если вы используете его в 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";
}

to

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», и, следовательно, ваш предел размера стека никогда не будет превышен.

person mshriv    schedule 11.08.2013
comment
да, я изменил свой код на итеративную процедуру! это сработало, кстати, как/где я могу написать, что размер стека не ограничен? - person activatedgeek; 13.08.2013
comment
Вы должны дать команду в оболочке до запуска вашего двоичного файла. Кстати, ограничение — это команда csh/tcsh. Если вы используете bash, сделайте ulimit -s неограниченно - person mshriv; 13.08.2013