All permutations of a string - how does this work?!

[Arslan7041]

Below is a code that prints all permutations of a string. I wanted to know how it worked, so I tried tracing (by pen and paper) but its quite difficult and im getting really confused.

#include <iostream>
#include <cstring>

using namespace std;

void permute (char[], int, int);
int main()
{
    char a[] = "123";
    int n = strlen(a)-1;
    permute(a, 0, n);

    return 0;
}

void permute(char a[], int i, int n)
{
   int j, temp;
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);
          cout << "-------->" << a << endl;  // I added this line myself
          permute(a, i+1, n);
          cout << "-------->" << a << endl;  // I added this line myself
          swap(a[i], a[j]);

       }
   }
}

Can someone walk me through this step by step? I would really appreciate it.

[ne555]

line 29 is to revert the changes done in line 25
line 25 is to chose the "first" element.

The idea to find all the permutations is to fix the first element and then find all the permutations on the rest.
This is the output for 4 elements

1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3214
3241
3124
3142
3412
3421
4231
4213
4321
4312
4132
4123

analysing the first 6 outputs

1234
1243
1324
1342
1432
1423

note how the '1' is fixed and then you have all the permutations of {2,3,4}
and seeing the first two

1234
1243

the '2' is fixed and you have all the permutations of {3,4}

[wizebin]

I had a hard time with permutation algorithms at first as well. The goal is to swap every character with every other character.

This is a recursive function that does that for every possible route and returns to the parent function when it has swapped out the last pair.

Does this help?

#include <iostream>
#include <string>
#include <functional>

using namespace std;

//Quick permutation function with callbacks
void permuteRef(string& str,int first,function<void(const string&)> callback){
    //if we have exhausted all possible swaps, this is a permutation
    if (first==str.size()){
        if (callback!=NULL){
            callback(str);
        }
    }
    else{
        //we have more characters to swap on this path
        for(int current = first; current < str.size(); current++){
            swap(str[first],str[current]);
            //branch our permutation to all sub permutations of this instance
            permuteRef(str,first+1,callback);
            swap(str[first],str[current]);
            //restore original value
        }
    }
}
//helper function, makes it simple to permute static strings or standard strings
void permute(const string& str, function<void(const string&)> callback){
    string subject = str;
    permuteRef(subject,0,callback);
}


int main(int argc, char* argv[]){
    //if you use a lambda, make sure you don't capture any variables
    permute("Hello",[](const string& str){cout << str << "\n";});
    
    return 0;
}

[Arslan7041]

ne555 I understand the technique used. What I can't understand is how the code implements it.

Here is the code again, with the two lines that I had added myself removed:

#include <iostream>
#include <cstring>

using namespace std;

void permute (char[], int, int);
int main()
{
    char a[] = "123";
    int n = strlen(a)-1;
    permute(a, 0, n);

    return 0;
}

void permute(char a[], int i, int n)
{
   int j, temp;
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);
          permute(a, i+1, n);
          swap(a[i], a[j]);

       }
   }
}

Now, in line 26, the function permute is recursively called. Therefore we go back to the beginning of the function to reset all the parameters and variables with the new arguments passed. This happens every time we hit line 26, so how does the code ever reach line 27?

Also, with each recursive call, will the code break out of the for-loop? How is the for-loop working in this code?

I need a simple break-down.

Wizebin, thank you but that does not help. Im not familiar with the 'functional' header file.

Please keep in mind that im a beginner.

[wizebin]

I need a simple break-down.

You really don't. You really, truly, seriously don't. You are a programmer, you create things, even if you're a beginner you have the logical facilities to understand anything in the known universe. Don't sell yourself short, don't give up because it seems hard to understand. Keep trying, it doesn't matter how we explain it here, you will still need to grasp the concept yourself. Use a debugger, keep trying with a pen and paper, come up with a solution for the permutation problem on your own, write out how you would do it, but don't expect us or anyone else to do your mental leg work for you now or in the future. It will get more abstract and more difficult from here, you are capable, you are intelligent, you can do it. Build the groundwork now so you can solve any problem later.

I could continue, but you get the idea. You have the ability- don't let yourself think you don't.

Anyways, on to the answers to your specific questions.

1. How does it reach 27? It reaches 27 AFTER it calls the sub function, that sub function returns after it does the same thing for each sub permutation.

2. Your code will NEVER break out of a for loop without your explicit instruction (few exceptions, including exceptions and force)

[Arslan7041]

Okay, I'll try again and come back with any questions. Thank you for the motivational rant :)

[dhayden]

Therefore we go back to the beginning of the function to reset all the parameters and variables with the new arguments passed

Here is your misunderstanding. When you call a function recursively in C++, the second call gets a new set of parameters and local variables.

[TheIdeasMan]

wizebin wrote:

2. Your code will NEVER break out of a for loop without your explicit instruction (few exceptions, including exceptions and force)

The base case is on line 19 of the OP's last code. if (i == n) this then executes line 27 and the function ends.

Edit:

I see what you are saying (I misread it a little), so this is more for the benefit of the OP.

[Arslan7041]

Here is your misunderstanding. When you call a function recursively in C++, the second call gets a new set of parameters and local variables

Here is what I understand about recursion.

When a function is called recursively, a copy of the function is made with those new parameters. If another recursive call happens, then another copy is made. All these copies are put on the stack. Once the base case is met, the function returns and one by one the copies on the stack pop off.

So in the 'permute' function, line 27 will NOT be reached until the base case is met. Once the base case condition is true, then line 27 will execute, along with the entire for-loop (all the iterations will be completed for each copy on the stack).

Please let me know if my understanding is correct.

[Arslan7041]

Okay, I honestly cannot make sense of this. I added couts to show the values of i and j as they change, but im still confused.

#include <iostream>

using namespace std;

void permute(char[], int, int);

int main()
{
   char a[] = "1234";
   int str_length = strlen(a)-1;
   permute(a, 0, str_length);
   return 0;

}

void permute(char a[], int i, int n)
{
   int j;
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);
          cout << "FIRST SWAP DONE! - i = " << i << " ---- j = " << j << endl;
          permute(a, i+1, n);
          swap(a[i], a[j]);
          cout << "SECOND SWAP DONE!- i = " << i << " ---- j = " << j << endl;
       }
   }
}

Here is the output:

FIRST SWAP DONE! - i = 0 ---- j = 0
FIRST SWAP DONE! - i = 1 ---- j = 1
FIRST SWAP DONE! - i = 2 ---- j = 2
1234
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
1243
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 1
FIRST SWAP DONE! - i = 1 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 2
1324
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
1342
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 2
FIRST SWAP DONE! - i = 1 ---- j = 3
FIRST SWAP DONE! - i = 2 ---- j = 2
1432
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
1423
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 3
SECOND SWAP DONE!- i = 0 ---- j = 0
FIRST SWAP DONE! - i = 0 ---- j = 1
FIRST SWAP DONE! - i = 1 ---- j = 1
FIRST SWAP DONE! - i = 2 ---- j = 2
2134
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
2143
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 1
FIRST SWAP DONE! - i = 1 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 2
2314
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
2341
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 2
FIRST SWAP DONE! - i = 1 ---- j = 3
FIRST SWAP DONE! - i = 2 ---- j = 2
2431
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
2413
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 3
SECOND SWAP DONE!- i = 0 ---- j = 1
FIRST SWAP DONE! - i = 0 ---- j = 2
FIRST SWAP DONE! - i = 1 ---- j = 1
FIRST SWAP DONE! - i = 2 ---- j = 2
3214
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
3241
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 1
FIRST SWAP DONE! - i = 1 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 2
3124
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
3142
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 2
FIRST SWAP DONE! - i = 1 ---- j = 3
FIRST SWAP DONE! - i = 2 ---- j = 2
3412
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
3421
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 3
SECOND SWAP DONE!- i = 0 ---- j = 2
FIRST SWAP DONE! - i = 0 ---- j = 3
FIRST SWAP DONE! - i = 1 ---- j = 1
FIRST SWAP DONE! - i = 2 ---- j = 2
4231
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
4213
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 1
FIRST SWAP DONE! - i = 1 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 2
4321
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
4312
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 2
FIRST SWAP DONE! - i = 1 ---- j = 3
FIRST SWAP DONE! - i = 2 ---- j = 2
4132
SECOND SWAP DONE!- i = 2 ---- j = 2
FIRST SWAP DONE! - i = 2 ---- j = 3
4123
SECOND SWAP DONE!- i = 2 ---- j = 3
SECOND SWAP DONE!- i = 1 ---- j = 3
SECOND SWAP DONE!- i = 0 ---- j = 3

I was doing fine until the first "1=2 ---- j = 3". Then I got lost as to how "1243" is printed. I understand how the 4 and 3 are swapped, but how does the cout statement execute? Im confused because j++ causes j to be larger then n, thereby exiting the loop. So now how does it go from exiting the loop to the cout statement? Seems like a random jump...

[dhayden]

I was doing fine until the first "1=2 ---- j = 3". Then I got lost as to how "1243" is printed. I understand how the 4 and 3 are swapped, but how does the cout statement execute?

It prints i=2 ---- j = 3" at line 26. So now the contents of the string is 1243. Next it executes line 27, which calls permute(a,3,3). This call hits the base case at line 19 so it prints 1243 at line 20 and exits.

It might be clearer to see how the function is called. Consider this change:

void permute(char a[], int i, int n)
{
   int j;
   cout << "Entering permute(" << a << ", " << i << ", " << n << ")\n";
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);
          permute(a, i+1, n);
          swap(a[i], a[j]);
       }
   }
   cout << "Leaving permute(" << a << ", " << i << ", " << n << ")\n";
}

Entering permute(1234, 0, 3)
Entering permute(1234, 1, 3)
Entering permute(1234, 2, 3)
Entering permute(1234, 3, 3)
1234
Leaving permute(1234, 3, 3)
Entering permute(1243, 3, 3)
1243
Leaving permute(1243, 3, 3)
Leaving permute(1234, 2, 3)
Entering permute(1324, 2, 3)
Entering permute(1324, 3, 3)
1324
Leaving permute(1324, 3, 3)
Entering permute(1342, 3, 3)
1342
Leaving permute(1342, 3, 3)
Leaving permute(1324, 2, 3)
Entering permute(1432, 2, 3)
Entering permute(1432, 3, 3)
1432
Leaving permute(1432, 3, 3)
Entering permute(1423, 3, 3)
1423
Leaving permute(1423, 3, 3)
Leaving permute(1432, 2, 3)
Leaving permute(1234, 1, 3)
Entering permute(2134, 1, 3)
Entering permute(2134, 2, 3)
Entering permute(2134, 3, 3)
2134
Leaving permute(2134, 3, 3)
Entering permute(2143, 3, 3)
2143
Leaving permute(2143, 3, 3)
Leaving permute(2134, 2, 3)
Entering permute(2314, 2, 3)
Entering permute(2314, 3, 3)
2314
Leaving permute(2314, 3, 3)
Entering permute(2341, 3, 3)
2341
Leaving permute(2341, 3, 3)
Leaving permute(2314, 2, 3)
Entering permute(2431, 2, 3)
Entering permute(2431, 3, 3)
2431
Leaving permute(2431, 3, 3)
Entering permute(2413, 3, 3)
2413
Leaving permute(2413, 3, 3)
Leaving permute(2431, 2, 3)
Leaving permute(2134, 1, 3)
Entering permute(3214, 1, 3)
Entering permute(3214, 2, 3)
Entering permute(3214, 3, 3)
3214
Leaving permute(3214, 3, 3)
Entering permute(3241, 3, 3)
3241
Leaving permute(3241, 3, 3)
Leaving permute(3214, 2, 3)
Entering permute(3124, 2, 3)
Entering permute(3124, 3, 3)
3124
Leaving permute(3124, 3, 3)
Entering permute(3142, 3, 3)
3142
Leaving permute(3142, 3, 3)
Leaving permute(3124, 2, 3)
Entering permute(3412, 2, 3)
Entering permute(3412, 3, 3)
3412
Leaving permute(3412, 3, 3)
Entering permute(3421, 3, 3)
3421
Leaving permute(3421, 3, 3)
Leaving permute(3412, 2, 3)
Leaving permute(3214, 1, 3)
Entering permute(4231, 1, 3)
Entering permute(4231, 2, 3)
Entering permute(4231, 3, 3)
4231
Leaving permute(4231, 3, 3)
Entering permute(4213, 3, 3)
4213
Leaving permute(4213, 3, 3)
Leaving permute(4231, 2, 3)
Entering permute(4321, 2, 3)
Entering permute(4321, 3, 3)
4321
Leaving permute(4321, 3, 3)
Entering permute(4312, 3, 3)
4312
Leaving permute(4312, 3, 3)
Leaving permute(4321, 2, 3)
Entering permute(4132, 2, 3)
Entering permute(4132, 3, 3)
4132
Leaving permute(4132, 3, 3)
Entering permute(4123, 3, 3)
4123
Leaving permute(4123, 3, 3)
Leaving permute(4132, 2, 3)
Leaving permute(4231, 1, 3)
Leaving permute(1234, 0, 3)

[ne555]

> a copy of the function is made
¿what do you mean with a copy?
functions are not objects.


> I added couts to show the values of i and j as they change
run through a debugger, there you can see the call stack and the variables.