Before I start, I have to apologize for bringing up another case of permutations with duplicates. I have gone through most of the search results and can’t really find what I am looking for. I have read about the Lexicographical order and have implemented it. For this question, I am suppose to implement a recursion method that prints out the all the strings of length n consisting of just the characters a and b that have an equal number of a and b’s. The strings must be printed out one line at a time in lexical order. So, for example, a call:
printBalanced(4);
will print the strings:
aabb abab abba baab baba bbaa
here is the code
public static void main(String[] args){ printBalanced(4); } public static void printBalanced(int n){ String letters = ""; //string to be duplicates of "ab" depending the number of times the user wants it for(int i =0; i<n/2;i++){ letters += "ab"; } balanced("",letters); } private static void balanced(String prefix, String s){ int len = s.length(); //base case if (len ==0){ System.out.println(prefix); } else{ for(int i = 0; i<len; i++){ balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len)); } } }
My print results:
abab abba aabb aabb abba abab baab baba baab baba bbaa bbaa aabb aabb abab abba abab abba baba baab bbaa bbaa baab baba
As you can see, I get a lot of duplicates. This is partly due to the requirement to use only characters ‘a’ and ‘b’. The duplicates will not happen if it was “abcd” or “0123”. I have read about using an arraylist and store all the results and then loop through N elements to check for duplicates and then removing it. This does not seem to be the best way to do it. Can someone share about other better solutions for this problem? =)
My Solution using SortedSet:
import java.util.Iterator; import java.util.SortedSet; import java.util.TreeSet; public class BalancedStrings { public static void main(String[] args){ printBalanced(4); } public static void printBalanced(int n){ String letters = ""; for(int i =0; i<n/2;i++){ letters += "ab"; } SortedSet<String> results = balanced("",letters); Iterator<String> it = results.iterator(); while (it.hasNext()) { // Get element and print Object element = it.next(); System.out.println(element); } } //This method returns a SortedSet with permutation results. SortedSet was chosen for its sorting and not allowing //duplicates properties. private static SortedSet<String> balanced(String prefix, String s){ SortedSet<String> set = new TreeSet<String>(); int len = s.length(); //base case if (len == 0){ //return the new SortedSet with just the prefix set.add(prefix); return set; } else{ SortedSet<String> rest = new TreeSet<String>(); for(int i = 0; i<len; i++){ //get all permutations and store in a SortedSet, rest rest = balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len)); //put each permutation into the new SortedSet set.addAll(rest); } return set; } }
}
Advertisement
Answer
You can use a Set and store the results in it (preferably SortedSet) this will eliminate duplicates and maintain a sorted order as well while traversal.