Recursive function here?

[dhanh90]

I have the problem like that ". Write a short Java program that outputs all possible strings formed by using the character ‘c’, ‘a’,’r’, ‘b’, ‘o’ , and ‘n’ exactly one."..and the code here:

public class StringPermutation {

//----------------------------------------------------------------------------

        private static char source[] = {'c', 'a', 'r', 'b', 'o', 'n'};

        private static char result[] = new char[6];

        private static boolean picked[] = new boolean[6];

//----------------------------------------------------------------------------

        public static void main(String[] args) {

                     // initialize that none of characters was picked

                     java.util.Arrays.fill(picked, false);

 

                     pickCharAt(0);

        }

//----------------------------------------------------------------------------        

        private static void pickCharAt(int position) {

                     // print out if 6 positions already filled

                     if (position > 5)

                                  System.out.println(String.valueOf(result));

                     // pick a remain character for current position

                     else

                                  for (int i=0; i<6; i++) {

                                                // if the character source[i] still not picked then pick it

                                                if (!picked[i]) {

                                                     result[position] = source[i];

                                                     picked[i] = true;

                                                     // fetch for next position

                                                     pickCharAt(position + 1);

                                                     // return the character source[i] when recur back

                                                     picked[i] = false;

                                        }

        }

}

I don't understand the pickChartAt function much..could someone show me how it work..and when it stops?
Thanks....

[stephen84s]

Why do you want us to explain your own code ?

[apines]

The recursion is checking all the possible permutations of the sources[] array. If you were given the task to write all the permutations, one approach would be to just:

1. Fix the number of the first letter.
2. See all the permutations of the n-1 letters remaining.

To see the permutation of all the rest of the n-1 letters remaining you would have done the same:

1. Fix the number of the first letter.
2. See all the permutations of the n-2 letters remaining.

And so one, until you would have reached the last letter, then every letter that you place is a new permutation.

this is exactly how the algorithm of this recursion works. It sets the result array to be some letter, and check all the other permutations of the rest of the places, until it reaches the last place - meaning when position is higher than 5 (that means we fixed all the possible letters in the array) and then it simply prints it:

if (position > 5)
{ 
   System.out.println(String.valueOf(result));
}

Let's try and understand how does it do it. From the main method we are calling pickCharAt(0); , meaning that position = 0 :

for (int i=0; i<6; i++) 
{
   // if the character source[i] still not picked then pick it
   if (!picked[i]) 
   { 
      result[position] = source[i];
      picked[i] = true;
      // fetch for next position
      pickCharAt(position + 1);
      // return the character source[i] when recur back
      picked[i] = false;
   }
}

Every iteration we are fixing result[position] to be a different letter from the source. Meaning when we exit the loop, every possible letter was in result[position] . Now, on line 9 we are calling the same method again, with the next position - we are doing the same procedure of iterating over all the possible letters that are in source[] and placing them in the result[position] array. Now all is left is to be sure that we are not using the same letter twice! We do that using the picked[] array - every iteration the first thing we check (line 4) is if the letter have already been picked in previous calls (meaning that it is now already placed in the result array in a previous position). If it is picked, we don't use it and move to the next letter. At the end of the iteration, we free the letter that we used (we will not use it during the next iteration) by making its cell in the picked[] array false (meaning its not picked and other calls can use it).

Recursions can be mind-blowing and don't be alarmed if you don't understand them right away. They are hard to explain as well and I hope you understood me - If I have confused you tell me what you didn't understand and I will try to explain again.

I remember that one of the professors at the university once said about recursions that they are a leap of faith - you need to believe that they will do what you want them to do ;)

[dhanh90]

Thanks a lot. I'm trying the understand it step by step...is there any version for this recursive approach?...i mean also using recursive but make it clearer to understand:d....

[apines]

What do you mean?

[dhanh90]

Suppose i have string "abcd"...now i want to use recursive to do permutation...using string.substring...something like that..to make algorithm clearer...

[dhanh90]

something like " ^ B ^ C ^ and ^ C ^ B ^
ABC BAC BCA ACB CAB CBA..."

[apines]

You want different code to do the same algorithm?