Java Program to Permute All Letters of an Input String

«
»

This is the Java Program to Print all Possible Permutations of a String.

Problem Description

Given a string, print all the different words that can be formed by permuting its letters.

Example:
String str =”ABC”;

Output =
ABC
ACB
BAC
BCA
CAB
CBC

Problem Solution

The solution to this problem is based on the programming paradigm backtracking. The idea used here keep a character constant and find the permutations of the remaining (n-1) characters. However, in case of strings having repeated characters, some strings are printed repeatedly.

Program/Source Code

Here is the source code of the Java Program to Print all Possible Permutations of a String. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

advertisement
advertisement
  1.  
  2. //Java Program to Print all Possible Permutations of a String
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class PermutationsOfAString {
  8.     // Function to swap two characters
  9.     static String swap(String str, int i, int j){
  10.         char ch;
  11.         char[] array = str.toCharArray();
  12.         ch = array[i];
  13.         array[i] = array[j];
  14.         array[j] = ch;
  15.         return String.valueOf(array);
  16.     }
  17.     // Function to print all the permutations of the string
  18.     static void permute(String str,int low,int high){
  19.         if(low == high)
  20.             System.out.println(str);
  21.  
  22.         int i;
  23.         for(i = low; i<=high; i++){
  24.             str = swap(str,low,i);
  25.             permute(str, low+1,high);
  26.             str = swap(str,low,i);
  27.         }
  28.     }
  29.     // Function to read user input
  30.     public static void main(String[] args) {
  31.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  32.         String str;
  33.         System.out.println("Enter a string");
  34.         try{
  35.             str = br.readLine();
  36.         }catch (Exception e){
  37.             System.out.println("An error occurred");
  38.             return;
  39.         }
  40.         System.out.println("All the possible permutations of "+ str + "are");
  41.         permute(str,0,str.length()-1);
  42.     }
  43. }
Program Explanation

1. In function swap(), firstly the string is converted into a character array.
2. Secondly, the characters at ith and jth indexes are interchanged and the character array is finally converted back to string.
3. In function permute(), firstly the low and high indexes are compared if(low == high), to see if they are equal.
4. If it is, that means we are processing the last character and no more permutations can be generated. So the string is printed.
5. The loop for(i = low; i<=high; i++) is used to generate all the permutations of the string.
6. Firstly, the character at low and i are swapped using swap(str, low, i). Then keeping this character constant, all the other permutations are generated using permute(arr,low+1, high).
7. Finally, the initially swapped character is swapped back to its original position.

Time Complexity: O(n*(n!) ) where n is the length of the string.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter a string
ABC
All the possible permutations of ABC are
ABC
ACB
BAC
BCA
CBA
CAB
 
Case 2 (Simple Test Case - another example):
 
Enter a string
ABCA
All the possible permutations of ABCA are
ABCA
ABAC
ACBA
ACAB
AACB
AABC
BACA
BAAC
BCAA
BCAA
BACA
BAAC
CBAA
CBAA
CABA
CAAB
CAAB
CABA
ABCA
ABAC
ACBA
ACAB
AACB
AABC

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.