Redirecting to
NADOS


  Prev   Next

Permutations-Words 2







Happiness can be found, even in the darkest of times, if one only remembers to turn on the light.
~Albus Dumbledore

Permutations-Words 2

Welcome back coder to yet another question of Permutations.

We suggest you go through all the previous questions for Combinations and Permutations, to get a better insight in this question.

You should also go through the problem link of this question, to get an outline of the problem.


Important Links : Problem Link, Solution Video


You are given a word (may have one character repeat more than once) and you are required to generate and print all arrangements of these characters.

We first revise permutations.

If we are given n boxes and r distinct objects, then the number of ways by which these r objects can be put into n boxes is denoted by nPr.

img

Hence, if we had 3 boxes and 2 distinct objects (1 and 2), then figure 2 shows all the six permutations.

img

You must notice that the input given by the problem, "aabb" also has 2 distinct objects (a and b).

We first see how to solve the problem for the objects (1 and 2) to be put into 3 boxes and after that relate it to the input given in the question.

img

Figure 3 shows us two methods of solving the given problem for 3 boxes and 2 distinct items (1 and 2). We study each of them one by one.

Approach :
Method 1- using items on levels:
img

In this method, we first decide item 1 as the level. For item 1, we have 3 choices, to keep it in box 1 or box 2 or box 3.

Now, for the next level we take item 2. It has only 2 choices each time because one of the three boxes is previously filled with item 1.

The last level of the tree in Figure 4, gives us all the possible permutations.

Method 2- using boxes on levels:
img

We suppose the initial level in which all the boxes are empty is the 0th level.

  • In this method, we decide the first level for box 1. Box 1 has 3 choices, it can either choose to remain empty, or have item 1 in it or have item 2 in it.
  • Now, for the next level for box 2, when all the boxes are empty, box2 has 3 options: to remain empty, to have item 1 in it or to have item 2 in it.
    However for the second level, when one of the boxes has been previously filled by an item, then box 2 has only 2 options: to remain empty or to have the item other than the one put in box1.
    This has been shown in the second level of the figure.
  • Again, this above process is repeated for box 3 in level 3.
  • The last level shows us all the possible permutations, but we only choose those as our final answer in which both the items are present (red marked permutations).

We suggest you go through the solution video to understand these trees better.

Now we relate the above methods with our input string "aabb" with 2 distinct items (a and b).

img
  • In the previous question, we used method 2 to solve this problem. Now we are going to solve it using method 1 by taking the items as the levels.
  • In figure 6, we first consider item 'a' as the first level. This 'a' has 4 options: to go in box 1 or box 2 or box 3 or box 4.
  • Now, we consider the next 'a' for the second level. For finding the permutations, this 'a' could have been put in any of the 3 remaining boxes.
    However, to prevent duplicity within the level, we put this 'a' in the boxes which come after the box of the previously filled 'a'.
  • Moving on to the next item, 'b' we can fill it anywhere in the 2 remaining boxes because this item hasn't been used before.
  • As we saw earlier, to avoid duplicity, the last item which is again a 'b' is put in those boxes which are after the box of the previous 'b'.
  • Hence we obtain all the desired permutations in the last level of the tree which are highlighted with green.
HOW

Reader, the code for the above explanation is quite simple. Refer to the code given below.

import java.io.*; import java.util.*; public class Main { public static void generateWords(int cc, String str, Character[] spots,HashMap< Character, Integer> lastOccurence) { //cc=current character if(cc==str.length()){ //1 for(int i=0;i< spots.length;i++){ System.out.print(spots[i]); } System.out.println(); return; } char ch=str.charAt(cc); //2 int lo=lastOccurence.get(ch); for(int i=lo+1;i< spots.length;i++){ //3 if(spots[i]==null){ spots[i]=ch; //4 lastOccurence.put(ch,i); generateWords(cc+1,str,spots,lastOccurence); //5 lastOccurence.put(ch,-1); //6 spots[i]=null; } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); Character[] spots = new Character[str.length()]; HashMap< Character, Integer> lastOccurence = new HashMap< >(); for(char ch: str.toCharArray()){ lastOccurence.put(ch, -1); } generateWords(0, str, spots, lastOccurence); } }
java; true";


  1. BASE CASE: If the "cc" becomes equal to the length of the string, we print the characters in all the spots and return from the function.
  2. We store the current character of the string in "ch". We also find out at what position was the last occurrence of this character and store it in "lo".
  3. We run the loop from the next position of the last occurrence of the character till the end of the array "spots". For every position, we check if the spot is empty.
  4. Then, we dump this character at the given position in the "spot" array.The value of "ch" is updated in the hashmap with the current position 'i'.
  5. Now we make a recursion call for the next item by increasing "cc" by 1.
  6. When backtracking, we put a value of "-1" against the character "ch" and put null at its position in the array "spots".
Analysis
Time Complexity:

O(n)

Space Complexity:

O(1) not including the space required for recursion stack.

Here, we conclude our discussion. We hope this question was clear to you.

If you still face any difficulties in this problem, we suggest you watch its solution video too.

Goodbye, we will see you with a new question.

Permutations Words-2
Recursion and Backtracking
Author: Shreeya Gupta
 
Run
Id Name