[Re-view] Recursive: Array Permutations

Intro

For the recursive function, it is very easy for most of us to write code for the fibonacci sequence. ( f(n)=f(n-1)+f(n-2) ). It seems we already got the idea of the recursion. What if you are asked to write the code for "8 queens problem" (actually this is also not hard at all) on a piece of paper? Some of you might feel  difficulty to rapidly and accurately do so. If you feel comfortable to write code for many recursive problem, you can definitely jump this post. But if you are easily confused facing slight complex recursive problems like me, maybe you wanna continue reading this post. From my experience, the 1st thing is to ask yourself, what are you thinking or what came out of you mind once you see a recursive problem? Recursion? Function argument list? Stop condition? for loop? Some lines of code?

Well, I'm neither good at remembering things, nor understanding things quickly. When I face the recursive problems, it's always a big mess! I just know this can be solved by recursion (and usually also DP, which is much harder), then I don't know what to do... So sad...

There is a saying that "Practice makes perfect" ! And "If you review the past, you will see new things!" In this post I will discuss the problem "Array permutation". I'll focus on the recursive procedure and present the way I remember the algorithm. Hopefully this will help you a little, but different people have different ways learning the same thing, try to find your own way, that is important.

Problem

Given an array of elements, return all the permutations.

e.g. Input: (1,2,3)

Return:  (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). 

Idea

First, we must make sure the problem can be solved using recursion. 

Usually, the problem which can be divided into sub problems is highly considered to be solvable using recursion.e.g. F(n)=F(n-1)+F(n-2). However, in this problem, it is not easy to see the sub problem. It may not work considering the length of the array, but it seems ok to consider each position. From the first element to the last... Every time I'm thinking of this, I have no way to go... 

Then I will remind myself about the recursion.  If the "function" e.g. f(n)=f(n-1)... cannot work, then I usually consider the following points:

1. Can I draw a Tree?
2. What are the stop/return conditions?
3. Does it need the backtracking?
4. Try to remember some standard code:
              func(){
                 if meet stop condition, return
                 else
                    for (i=1:n){
                        do something
                        func(next);
                        may need backtracking;
                    }
               }
      Despite this is not the master key solving the recursion, but it helps a lot when you have no idea at all.


If I can draw a tree, the problem is more straightforward and it related to the tree traversal problem, if you are familiar with that code, it would helps you a lot. If not, it is also easier to design the recursive function.

Stop/return condition is important. You have to think when your program will stop, when will it output the result. It is also the key to the recursion.

Backtracking is another issue when you do the "search", sometimes it is not needed, but sometimes you have to change back the status so that the search is not missing some branches. e.g., usually when there is loop in your recursion, be cautious!

For this problem, if you can draw a tree like this,  you are almost getting there! 

Then think about to construct the recursive function in your mind, see the tree and consider every node is a new function call:
Argument list: what we have to know in each recursion? The array and the length, the current position (a,n,k)
Stop condition: when all the positions are searched, print the output (if k==n)
Search rule:  swap current position with all the following positions (for i= k: n, swap)
Recursive:    fix current position, go to next position (perm(a, k+1,n))
Backtracking: needed! because there is a for loop, we swap the array before perm, so we swap back after.

Given these, writing code seems not hard then:

perm(int* A, int k, int n){
  if (k==n) {print(A); // print out the array, you can define by yourself}
  else{
    for (int i=k;i<n;i++){
      swap(A[i],A[k]); // swap the two values, you can define by yourself
      perm(A,k+1,n);
      swap(A[i],A[k]);
    }
  }
}

Some suggestions:

Please read the code carefully and according to the tree figure, you will find your own way understand that。
Please try to remember some classic recursive problems, don't have to remember every line of code, but the key lines or the structures of the function.
When you face a new problem, try to think the sub-problem, or the easy case (e.g. the number is 0 or 1).


I'll give more examples in the later posts.


(finished)