Algorithms
Permutation and Combination
Permutation means arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {a,b,c}, namely: (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), and (c,b,a). These are all the possible orderings of this three element set.
Combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. In smaller cases it is possible to count the number of combinations. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. If the input set is {a, b, c} then the output set is {a, ab, abc, ac, b, bc, c}.
There could be some variations of permutations/combinations such as finding permutations/combinations of k element from a set of n elements, with or without allowing repetition of an element. Also, we might need to find unique permutations in case the input string contains duplicate chars. Below are simple implementations of all these variations based on the prefix based approach illustrated by the figure above.
private static void kPermutation(String pref, String str, int k){
if(k == 0){
System.out.print(pref+", ");
}
else{
for(int i = 0; i<str.length(); i++){
kPermutation(pref+str.charAt(i), str.substring(0, i)+str.substring(i+1), k-1);
}
}
}
private static void PermutationWithRepts(String pref, String str, int k){
if(k == 0){
System.out.print(pref+", ");
}
else{
for(int i = 0; i<str.length(); i++){
PermutationWithRepts(pref+str.charAt(i), str, k-1);
}
}
}
public static void permutation(String str, int k, boolean repetitionAllowed){
if(k > 0 && k <= str.length()){
if(!repetitionAllowed)
kPermutation("", str, k);
else
PermutationWithRepts("", str, k);
System.out.print("\n");
}
}
private static void uniquePermutation(String pref, String str, int k, Set<String> visited){
if(!visited.contains(pref)){
if(k == 0){
System.out.print(pref+", ");
}
else{
for(int i = 0; i<str.length(); i++){
uniquePermutation(pref+str.charAt(i), str.substring(0, i)+str.substring(i+1), k-1, visited);
visited.add(pref+str.charAt(i));
}
}
}
}
public static void uniquePermutation(String str, int k){
if(k > 0 && k <= str.length()){
Set<String> visited = new HashSet<String>();
uniquePermutation("", str, k, visited);
System.out.print("\n");
}
}
private static void kCombination(String pref, String str, int k){
if(k == 0){
System.out.print(pref+", ");
}
else{
for(int i = 0; i<str.length(); i++){
kCombination(pref+str.charAt(i), str.substring(i+1), k-1);
}
}
}
public static void combination(String str, int k){
if(k > 0 && k <= str.length()){
kCombination("", str, k);
System.out.print("\n");
}
}
private static void allCombination(String pref, String str){
if(!pref.isEmpty())
System.out.print(pref+", ");
for(int i = 0; i<str.length(); i++){
allCombination(pref+str.charAt(i), str.substring(i+1));
}
}
public static void allCombination(String str){
allCombination("", str);
System.out.print("\n");
}
Permuting Lists of Lists
Now lets consider the following problem –
Given a list of arraylists containing elements, write a function that prints out the permutations of of the elements such that, each of the permutation set contains only 1 element from each arraylist and there are no duplicates in the list of permutation sets.
For example: consider the following lists
L1= {a1,b1,c1,d1}
L2= {a2,b2,c2}
L3= {a3, b3, c3}
Valid Permutations are:
{a1, a2, a3}
{a1, a2, b3}
{a1, a2, c3}
{a1, b2, a3}
{a1, b2, b3}
{a1, b2, c3}
...
...
...
{d1, c2, a3}
{d1, c2, b3}
{d1, c2, c3}
Please note that
{a1,b2,c3} is same set as {b2,a1,c3}
We can solve this problem similar to we did solve the combination problem where we consider the the input list as a multidimensional string that contains a list of string at each position. Anytime we will consider one single item. So, for each string in first list we do recurse to all other lists to find the combinations. We print the result whenever we reach the last list and output contains one elements from each of the n lists. Below is the implementation of this idea.
public static void permuteList(String[][] list, int start, ArrayList<String> perms){
if(start == list.length){
if(perms.size() == list.length)
System.out.println(perms.toString());
return;
}
for(int i = 0; i < list[start].length; i++){
perms.add(list[start][i]);
for(int j = start+1; j <= list.length; j++){
permuteList(list, j, perms);
}
perms.remove(list[start][i]);
}
}
Permuting All Cases of a String
Let’s consider another problem.
Given a String. Find all possible cases of the character in the String.
For example, Given a string “abcd” we should output all cases : [aBcD, AbCD, aBcd, ABCd, ABCD, aBCD, aBCd, AbCd, ABcd, ABcD, abCD, abCd, Abcd, abcD, AbcD, abcd].
The problem can be solved by trying both upper case and lower case permutation for each character and then recursively do the same for rest of the string. So, we will basically change to lower case of a character and then recursively try all cases for rest of the string. Then we will back track and change the character to upper case as then try all cases for the rest of the String. Below is the implementation of the above idea. The complexity of this approach however can be improved from exponential to O(n^2) using DP approach which I leaving as an exercise for the readers.
public static void allCasePermutataion(String str, int start, Set<String> res){
if(start == str.length()){
res.add(str);
return;
}
char[] chars = str.toCharArray();
chars[start] = Character.toLowerCase(chars[start]);
allCasePermutataion(new String(chars), start+1, res);
chars[start] = Character.toUpperCase(chars[start]);
allCasePermutataion(new String(chars), start+1, res);
}