Permutation
Permutation of a set is simply a different ordering of the elements. For the given string, we can order the characters into different locations producing different string. All such strings constitute the permutation of that string.
Example: Permutation of a string XYZ are:
XYZ XZY YXZ YZX ZXY ZYX
For given string of length n there are total of n! permutations.
XYZ XZY YXZ YZX ZXY ZYX
Algorithm - For String with Unique Characters
As explained HERE, following image explains how we can compute the permutations of given string.
In this algorithm,
- For each character in the input String:
- Select the character and keep it fixed.
- Compute permutations of remaining n−1 characters.
- Finally append all those permutations of n−1 characters to the character selected in the Step 1.
Algorithm - For String with Duplicate Characters
Algorithms described above will also work with strings with duplicate characters. However, the algorithm will also produce duplicate results. So a simple solution will be to check for unique solutions, probably using Hashing, in the above solution.Problem
The problem with this solution is, for a string with two many duplicate characters, it will end up computing all n! solutions while there are very few number of solutions.
Example: String AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA has only one permutation which the input string itself.
But the above algorithm will be doing a lot of unnecessary computation.
But the above algorithm will be doing a lot of unnecessary computation.
Solution
So for string with duplicate entries, we can write efficient solution. For string with all unique characters, its performance will still become n!.The solution is very much similar to the Coin Exchange Problem.
In this algorithm,
- We can create Frequency table which keeps count of all unique characters in the string.
- For each unique character if it count is Greater Than 0:
- Append the character to Current Permutation. When length of the Current Permutation is equal to the length of input string, we have one solution.
- Decrease count by 1.
- Recurse through the same updated Map.
- Reset or Increase the count by 1.
Implementation (Both Method)
Following is the implementation for both the method.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* File: Permutations.java
* Created: 10/1/2018
* Author: Sabbir Manandhar
*
* Copyright (c) 2018 Hogwart Inc.
*/
import java.util.*;
//=======================================================================================
/**
* @author Sabbir Manandhar manandharsabbir@gmail.com
* @version 1.0
*/
public class Permutations {
public static void main(String[] args) {
List<String> permutations = permutationWithoutDuplicates("ABCD");
for (String permutation : permutations)
System.out.println(permutation);
System.out.println();
permutations = permuteWithDuplicates("AAABB");
for (String permutation : permutations)
System.out.println(permutation);
} // main
//-------------------------------------------------------------------------------------
//------ Solution 1: For Input with Unique Characters Only -----------
/**
* Computes permutation of given string without any duplicate characters.
* For string duplicate character, results will contain duplicate entries.
* @param s input string
* @return List of permutations
*/
public static List<String> permutationWithoutDuplicates(String s) {
char[] chars = s.toCharArray();
List<String> permutations = new ArrayList<>();
permutationWithoutDuplicatesHelper(chars, 0, permutations);
return permutations;
} // permutationWithoutDuplicates
//-------------------------------------------------------------------------------------
/**
* Recursive helper method to compute permutations of a character array without duplicates.
* @param chars input character array
* @param cursor pointer to current location considered. Characters before this pointer and kept fixed.
* @param permutations List holding resulting permutations
*/
private static void permutationWithoutDuplicatesHelper(char[] chars, int cursor, List<String> permutations) {
if (cursor == chars.length) {
permutations.add(new String(chars));
return;
}
for (int i = cursor; i < chars.length; i++) {
swap(chars, cursor, i);
// keep the selected character fixed and compute permutations of remaining characters
permutationWithoutDuplicatesHelper(chars, cursor + 1, permutations);
swap(chars, cursor, i);
}
} // permutationWithoutDuplicatesHelper
//-------------------------------------------------------------------------------------
/**
* Utility method to swap two characters in the given character array.
* @param chars input character array
* @param i first index to swap.
* @param j second index to swap.
*/
private static void swap(char[] chars, int i, int j) {
if (i == j) return;
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
} // swap
//------ END Solution 1 ---------------------------------------------------------------
//-------------------------------------------------------------------------------------
//------ Solution 2: For Input with Duplicate Characters ------------------------------
/**
* Computes permutation of an string with Duplicate characters.
* Obviously, it will also work for the string with unique characters.
* @param s input string.
* @return Permutations of given input.
*/
public static List<String> permuteWithDuplicates(String s) {
char[] chars = s.toCharArray();
Map<Character, Integer> frequencyMap = createFrequencyMap(chars);
List<String> results = new ArrayList<>();
permuteWithDuplicatesHelper(frequencyMap, new char[s.length()], 0, results);
return results;
} // permuteWithDuplicates
//-------------------------------------------------------------------------------------
/**
* Recursive helper method to compute permutations of a string with duplicate characters.
* @param frequencyMap Map holding character counts of input.
* @param permutation current permutation
* @param cursor current location in permutation
* @param results List of all permutations of input.
*/
private static void permuteWithDuplicatesHelper(Map<Character, Integer> frequencyMap, char[] permutation, int cursor, List<String> results) {
if (cursor == permutation.length) {
results.add(new String(permutation));
return;
}
for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() > 0) {
permutation[cursor] = entry.getKey();
entry.setValue(entry.getValue() - 1);
permuteWithDuplicatesHelper(frequencyMap, permutation, cursor + 1, results);
entry.setValue(entry.getValue() + 1);
}
}
} // permuteWithDuplicatesHelper
//-------------------------------------------------------------------------------------
/**
* Utility method to create character counts as a Map.
* @param chars input character array
* @return Character Counts Map.
*/
private static Map<Character, Integer> createFrequencyMap(char[] chars) {
Map<Character, Integer> result = new HashMap<>();
for (Character c : chars) {
if (result.containsKey(c)) {
result.put(c, result.get(c) + 1);
} else {
result.put(c, 1);
}
}
return result;
} // createFrequencyMap
//------ END Solution 2 ---------------------------------------------------------------
} // Permutations
