Monday, May 2, 2022

Question 9 : Write a program to print all permutations of String in java?

 A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement. For instance, the words ‘bat’ and ‘tab’ represents two distinct permutation (or arrangements) of a similar three-letter word.


Examples: 
 

Input: str = “cd” 
Output: cd dc
Input: str = “abb” 
Output: abb abb bab bba bab bba 

Approach: Write a recursive function that prints every permutation of the given string. Termination condition will be when the passed string is empty.
Below is the implementation of the above approach:

:

public class CloudTechtwitter { static void printPermutn(String str, String ans) { if (str.length() == 0) { System.out.print(ans + " "); return; } for (int i = 0; i < str.length(); i++) { // ith character of str char ch = str.charAt(i); // Rest of the string after excluding // the ith character String ros = str.substring(0, i) + str.substring(i + 1); // Recursive call printPermutn(ros, ans + ch); } } // Driver code public static void main(String[] args) { String s = "abb"; printPermutn(s, ""); } }

Output: 
abb abb bab bba bab bba

 

When the permutations need to be distinct.
Examples: 
 

Input: str = “abb” 
Output: abb bab bba 

Approach: Write a recursive function that prints distinct permutations. Make a boolean array of size ’26’ which accounts for the character being used. If the character has not been used then the recursive call will take place. 

Otherwise, don’t make any calls. The termination condition will be when the passed string is empty.

Below is the implementation of the above approach:

public class CloudTechTwitter { // Function to print all distinct permutations of str static void printDistinctPermutations(String str, String ans) { if (str.isEmpty()) { System.out.print(ans + " "); return; } boolean[] used = new boolean[26]; // To track used characters for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); String remaining = str.substring(0, i) + str.substring(i + 1); if (!used[ch - 'a']) { printDistinctPermutations(remaining, ans + ch); used[ch - 'a'] = true; } } } public static void main(String[] args) { String s = "abba"; printDistinctPermutations(s, ""); } }


Output: 
abba abab aabb baba baab bbaa 

Don't miss the next article!

Be the first to be notified when a new article or Kubernetes experiment is published.                            

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS