String Permutaton Problems
Hi,
Today I am trying to solve two interesting problems in String Permutations:
1. Generate all permutation of a string with assumption that all characters are unique.
The idea is recursively choose ‘available” character to build a new string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | private boolean[] mask = null; private char[] charSeq = null; //print all permutation with non repetition public void permute(String str){ charSeq = new char[str.length()]; mask = new boolean[str.length()]; permutate(str,0); } private void permutate(String str,int index){ for (int i = 0; i < str.length();i++){ if (!mask[i]){ charSeq[index] = str.charAt(i); mask[i] = true; if (index == str.length() - 1) System.out.println(new String(charSeq)); else permutate(str,index+1); mask[i] = false; } } } |
2. Generate all permutation of a string without a “uniqueness” assumption like above.
The idea is to convert this problem into the 1st one by looking more closely on the “availability’ of characters. We can understand that in the problem one each character is unique and it has frequency is 1. In the problem, we still have a set of “unique” character. The only difference is the frequency of each character:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | private Hashtable charSet = new Hashtable(); static int count = 0; private char[] charSeq = null; public void permute22(String str){ count = 0; aSet.clear(); charSeq = new char[str.length()]; for (int i = 0;i < str.length(); i++){ char chr = str.charAt(i); if (!charSet.keySet().contains(chr)) charSet.put(chr,1); else charSet.put(chr,charSet.get(chr) +1); } permute22(str,0); } private void permute22(String str, int index){ if (index == str.length()){ System.out.println(++count+":"+new String(charSeq)); aSet.add(new String(charSeq)); } else{ for (char ch:charSet.keySet()){ if (charSet.get(ch) > 0){ charSeq[index] = ch; charSet.put(ch,charSet.get(ch)-1); permute22(str, index+1); charSet.put(ch,charSet.get(ch)+1); } } } } |
In future, I will collect and post more string generation/combination/generation problems.
PS: I found very interesting article about String Permutation here. Personally, I think the swapping idea is fantastic for the 1st problem. I do not think it works for the second problem with the assumption – two identical generation will happen sequentially because of sorting order. It is correct at the beginning. It is not correct during the swapping phase, however. At the middle of string generation by swapping, the order of its characters are not ordered anymore. I tested with my own source code and found the duplication in generation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | static int count = 0; static HashSet aSet = new HashSet(); private void QuickSort(char[] arr, int lower, int upper){ if (lower >= upper) return; swap(arr,lower, (lower+upper)/2); int pivot = lower; int pivotValue = arr[pivot]; for (int i = lower+1; i <= upper;i++){ //if ith element in wrong position if (arr[i] < pivotValue){ pivot++; swap(arr,pivot,i); } } //put the pivot into the correct position: <= pivotValue = pivotValue >= pivotValue swap(arr,lower,pivot); QuickSort(arr,lower,pivot-1); QuickSort(arr,pivot+1,upper); } public void permute2(String str){ count = 0; aSet.clear(); charSeq = str.toCharArray(); QuickSort(charSeq,0,charSeq.length-1); System.out.println("SORTED:"+new String(charSeq)); permute2(charSeq, 0); } private void swap(char[] arr,int i, int j){ if (i == j) return; char temp = arr[i];arr[i] = arr[j]; arr[j] = temp; } private void permute2(char[] charSeq, int index) { int lastSwap = -1; if (index == charSeq.length - 1) { String aString = new String(charSeq); System.out.println(++count+":"+ aString); if (aSet.contains(aString)) System.out.println("Collide:" + aString); else aSet.add(aString); } else { for (int i = index; i < charSeq.length; i++) { if (charSeq[i] != lastSwap) { lastSwap = charSeq[i]; swap(charSeq, i, index); permute2(charSeq, index + 1); swap(charSeq, i, index); } } } } |
.