CC-7 : Find all permutations of characters of String..

Description:

Given an input String, find all permutation of its constituent characters.

Test cases and expected outputs:

Input Parameters	Expected outputs
Original String: red	Permutations of characters: red rde erd edr dre der

Pseudocode:

findAllPermutations(str):

The String to be checked is received as input parameter.

If str.length==1 (base case):

Initialize new ArrayList named currentPermutation.

Add str to currentPermutation.

Return currentPermutation.

Initialize ArrayList named permutations to store all found permutations.

Iterate through characters of input String using for loop with I as iteration variable and values of i ranging from 0 to length of input str:

Set variable currentLetter to str.chatAt(i).

Set variable remainingLetters to resultant String after removing currentLetter from input str.

Set variable permulationsOfRemainingChars to return value of recursive call to findAllPermutations(remainingLetters).

Iterate through Strings of ArrayList permulationsOfRemainingChars using for loop with idx as iteration variable and values of idx ranging from 0 to length of permulationsOfRemainingChars:

Add String formed by adding currentLetter and permulationsOfRemainingChars.get(idx) to ArrayList permutations.

Return permutations as itnow contains all permutations of characters of input str.

Code:

public ArrayList<String> findAllPermutations(String str) {
	if (str.length() == 1) {
		ArrayList<String> currPermutation = new ArrayList<String>();
		currPermutation.add(str);
        return currPermutation;
    }
    ArrayList<String> permutations = new ArrayList<>();
    for (int i = 0; i < str.length(); i++) {
    	char currentLetter = str.charAt(i);
        String remainingLetters = str.substring(0, i) + str.substring(i + 1);
        ArrayList<String> permsOfRemainingLetters = findAllPermutations(remainingLetters);
        for (int idx=0; idx < permsOfRemainingLetters.size(); idx++) {
        	permutations.add(currentLetter+permsOfRemainingLetters.get(idx));
        }        
    }
    return permutations;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;

public class RecursionFindPermutations {

public ArrayList<String> findAllPermutations(String str) {
	if (str.length() == 1) {
		ArrayList<String> currPermutation = new ArrayList<String>();
		currPermutation.add(str);
        return currPermutation;
    }
    ArrayList<String> permutations = new ArrayList<>();
    for (int i = 0; i < str.length(); i++) {
    	char currentLetter = str.charAt(i);
        String remainingLetters = str.substring(0, i) + str.substring(i + 1);
        ArrayList<String> permsOfRemainingLetters = findAllPermutations(remainingLetters);
        for (int idx=0; idx < permsOfRemainingLetters.size(); idx++) {
        	permutations.add(currentLetter+permsOfRemainingLetters.get(idx));
        }        
    }
    return permutations;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	ArrayList<String> retVal;
	try {
	
	RecursionFindPermutations rcn=new RecursionFindPermutations();
	String str="red";
	retVal=rcn.findAllPermutations(str);
	System.out.println("Original String: "+str);
	for (int idx=0; idx < retVal.size(); idx++) {
		System.out.println(retVal.get(idx));
	}	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
}

}
}