Generating lexicographic permutations: Segmentation fault

Question

I have this code to generate lexicographic permutations. The following logic is used:

Start from the increasing order arrangement of the chars in a given test string.
To generate next lexicographic permutation:

a) find the rightmost character which is smaller than its next character. SAY A.

b) to the right of A, find the next larger character. SAY B. and swap A & B.

c) to the right of the original position of A, sort characters in an increasing order.

Algorithm ends when we get the last permutation. i.e. reverse of given test string. my test string s = "0123456789"

Edit: On every single run of the program, i get a separate position of segmentation fault.

to get 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;}

to get B and then recursive approach (qsort is a function from <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;}

starting func:

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";}

call from main: nextpermute(test);

If the test string is "01234567" or anything smaller than this, it works well. but if it is a string like "012345678" or "0123456789" , then i get segmentation faults. Please help!!

@chris i am trying to work this out myself. once thru, sure i would use that — activatedgeek
And why are you using strcmp with s.c_str() instead of operator== with s? You've managed to take safe code and make it unsafe. — chris
ohh yes! just slipped off my mind, i can compare the string objects directly. anyways that still doesn't solve my issue. — activatedgeek
If you are getting a seg-fault, you should run your code in a debugger to determine which line is causing the problem. Then work backwards from there. — Oliver Charlesworth

mshriv mshriv · Accepted Answer · 2013-08-11T12:26:09

I suspect your stack size is crossing its limit. If you are running it on Linux, do "limit" and see your stacksize. There are two ways to avoid this situation

1) (Not Recommended) Do "limit stacksize unlimited" (only if you are on unix based system). And run the program again.

2) (Recommended).

Change

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";
}

and modify your main function as

int main()
{
    string s = "0123456789";
    while (s != "9876543210")
    {
        nextpermute(s);
    }
}

Above change will do away with the recursion of "nextpermute" and hence your stacksize limit will never be crossed

Generating lexicographic permutations: Segmentation fault

1 Answers