Infinite loop

[adam2016]

Hi guys,

So I'm reading a book on data structures and algorithms and one of the challenge questions was to print out all permutations of a string ABC, so after a few failed attempts I decided to check out an algorithm to do this, after about an hour or two studying the algorithm in depth it started to make sense - https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ , the algorithm uses both iteration and recursion.

first we swap A with A and call permute with index+1 this means the A will be fixed or left untouched in the subsequent calls, in the next permute call i will index which in this case it will be 1, so we swap B with B and again essentially fix B in that position next we call permute again and since we hit our base case we print ABC and return from that function call, now we are back at the previous function call and we increment i to 2, we swap B with C, again essentially fixing AC and we call permute with index+1 and yet again we hit our base case and print ACB, we then return from this function, next we backtrack and swap C with B giving us ABC,

in this instance of permute ( remember we are again in the previous instance of permute that called permute(word,2,2), so again i will equal 1) index will equal 1 and i will also equal 1, so how does the function return??? after we have backtracked and swapped C with B giving us ABC won't i not be incremented again giving us i = 2 since we are in a for loop??

so shouldn't this infinitely print ACB? as the for loop will next increment again to 2 and since i is now 2 again we swap B with C giving us ACB and yet again we call permute with index = 2 and print ACB??

but it seems like once we have backtracked the for loop terminates even when i = 1 in that callees stack frame.

thanks

void permute(string& word, int index,int size){

     if(index == size){

        cout << word << endl;
     }else{

        for(int i = index; i <= size; ++i){

           swap(word.at(i),word.at(index));
           permute(word,index+1,size);
           swap(word.at(i),word.at(index));
        }
     }
}

int main()
{
    string str = "ABC";
    permute(str,0,3);
}

[adam2016]

sorry guys,

my bad, in retrospect that actually makes little sense , the loop will indeed finish.




(hopefully this will help anybody who ever encounters the same problem)

lets say on permute("ABC",1,2)

i will = 1, index will = 1 , size = 2, string will = "ABC"

1) we swap i with index  (B with B)
2) call pemute("ABC",2,2)
3) permute ("ABC",2,2) hits the base case prints "ABC " and returns
4) we swap i with index (B with B) // back track
5) i will now equal 2
6) we swap i with index (C with B)
7) call permute("ABC",2,2)
8) permute ("ABC",2,2) hits the base case prints "ACB " and returns
9) we swap i with index (B with C) // back track
10) i will now equal 3 so loop terminates.

I must have drawn my recursive tree wrong and somehow mixed up a detail or two, also another contributing factor was possibly me over thinking the whole process.

Thanks