Generating lexicographic permutations: Segmentation fault

Question

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

1. Start from the increasing order arrangement of the chars in a given test string.
2. 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!!

Answer 1

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