Home > Algorithms, Java > String Permutaton Problems

String Permutaton Problems

March 2nd, 2010 NamPham Leave a comment Go to comments

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.

2. Generate all permutation of a string without a “uniqueness” assumption like above.

Here is the detail:

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.

?View Code JAVA
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:

?View Code JAVA
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.

?View Code JAVA
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);
				}
			}
		}
	}
Categories: Algorithms, Java Tags: , , ,
  1. Kang
    March 3rd, 2010 at 22:56 | #1
    Reply | Quote

    for (int i = 0; i < str.length();i++){
    ?

  2. NamPham
    March 3rd, 2010 at 23:02 | #2
    Reply | Quote

    Sorry, there is a wrong conversion from code in html page.
    The correct one is:
    for (int i = 0; i < str.length();i++)

  1. June 13th, 2010 at 11:49 | #1
    Kylie Batt1