Can someone explain me this code which generates all the possible permuations of a given set?

1
votes

I found a recursion code in the competitive programmer's handbook to do the same but I'm struggling to understand the logic behind it.
It states that:

Like subsets, permutations can be generated using recursion. The following function search goes through the permutations of the set {0,1,...,n¡1}. The function builds a vector permutation that contains the permutation, and the search begins when the function is called without parameters. 

void search() {
    if (permutation.size() == n) {
        // process permutation
    } else {
        for (int i = 0; i < n; i++) {
            if (chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

Each function call adds a new element to permutation. The array chosen indicates which elements are already included in the permutation. If the size of permutation equals the size of the set, a permutation has been generated.

I can't seem to understand the proper intuition and the concept used.
Can somemone explain me what the code is doing and what's the logic behind it?

2
c++algorithmrecursionsetpermutation
Run it with pencil and paper using n == 3. – n. 1.8e9-where's-my-share m.
You add each element one by one to the current permutation, then you recurse to generate all permutations of remaining elements with this "prefix", after which you remove the current element at this level again and proceed with the next until there are no more left to try. – 500 - Internal Server Error
there is a better solution by using: std::next_permutation. – Marek R

2 Answers

4
votes

I will try to give you some intuition . The main idea is to backtrack . You basically build a solution until you face a dead end. When you do face a dead end , go back to the last position where you can do something different than what you did the last time . Let me walk through this simulation I have drawn for n = 3 .

enter image description here

First you have nothing . Take 1 , then 2 and then 3 . You have nowhere to go now i.e Dead End . You print your current permutation which is 123 What do you do now ? go back to 1 because you know you can make another path by taking 3 this time . So what do you get this time the same way ? 132 . Can you do anything more using 1 ? Nope . Now go back to having nothing and start the same thing over , now taking 2 . You get the point now , right ?

For the same thing which is happening where in the code :

void search() {
    if (permutation.size() == n) /// DEAD END
    { 
        // process permutation
    } 
    else {
        for (int i = 0; i < n; i++) {

            if (chosen[i]) continue; /// you have already taken this in your current path , so ignore it now

            chosen[i] = true; /// take it , as you haven't already
            permutation.push_back(i);

            search(); // go to the next step after taking this item

            chosen[i] = false; // you have done all you could do with this , now get rid of it
            permutation.pop_back();
        }
    }
}
3
votes

You can split up the code like this:

void search() {
    if (permutation.size() == n) {
        // we have a valid permutation here
        // process permutation
    } else {

        // The permutation is 'under construction'.
        // The first k elements are fixed,
        // n - k are still missing.
        // So we must choose the next number:
        for (int i = 0; i < n; i++) {

            // some of them are already chosen earlier
            if (chosen[i]) continue;

            // if i is still free:

            // signal to nested calls that i is occupied
            chosen[i] = true;
            // add it to the permutation
            permutation.push_back(i);

            // At the start of this nested call,
            // the permutation will have the first (k + 1)
            // numbers fixed.
            search();

            // Now we UNDO what we did before the recursive call
            // and the permutation state becomes the same as when
            // we entered this call.
            // This allows us to proceed to the next iteration
            // of the for loop.

            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

The intuition could be that search() is "complete the current partially constructed permutation in every way possible and process all of them".

If it is already complete, we only need to process the one possible permutation. If not, we can first choose the first number in every way possible, and, for each of those, complete the permutation recursively.