Archive

Archive for the ‘Algorithms’ Category

String Permutaton Problems

March 2nd, 2010 NamPham 2 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.

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: , , ,

Hashing in Java

February 28th, 2010 NamPham No comments

This is my summary after reading a wonderful article from ibm (Java theory and practice: Hashing it out.

In my understanding, every object in Java has two implemented methods hashCode() and equals() to identify each object to others. A general rule is that two objects are equal to each other, they have the same hashcode (but the reverse is may not be true – and it is called collision).

Generally, we want to override both of them because of their relationship as mentioned above.

There are some requirements when you override two methods:

For equals(), it should:

Symmetry: a.equals(b) == b.equals(a)

Transitivity: a.equals(a) = true;

Reflexivity:  a.equals(b) == true, b.equals(c) == true -> c.equals(a) == true;

For hashCode():

Consistency: if a.equals(b) == true then a.hashCode() == b.hashCode()

Normally, when you implement the hashCode() method, we should not change the object’s hashCode() on the fly. Especially when we use a collection of objects, theirs hashCode should stay the same to avoid some unpredictable result. And we can refer these such objects as immutable objects – which their states do not change after it is constructed.
Finally, here are the interface for both two methods:

?View Code JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public boolean equals(Object object){
 
if (this == object) return true;
 
if (!this.getClass().equals(object.getClass())  return false;
 
return sth;
 
}
 
public int hashCode(){
 
return sth;
 
}

Java theory and practice: Hashing it out

Categories: Java Tags:

Binary Search

January 19th, 2010 NamPham No comments

As a programmer, most of us have at least coded the binary search algorithm: the algorithm to find a value in a sorted array. The algorithm itself is clear and easy to understand:

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11

int BinSearch::bSearch(int* arr,int n, int value){
	int left = 0;
	int right = n;
	while (left <= right){
		int mid = (int)(left+right)/2;
		if (arr[mid] == value) return mid;
		else if (arr[mid] < value) left = mid + 1;
		else right = mid - 1;
	}
	return -1;
}

However, the binary search algorithm’s capability is far beyond that. Given an array of number (real/int), we can find the element in that array which is closest to the given value. The idea is that we find a range [left,right] in array that is small enough and “close enough” to value .i.e a[left] < value < a[right], value < a[left] < a[right] or a[left] < a[right] < value:

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12

int BinSearch::bNearSearch(int* arr, int n, int value){
	int left = 0;
	int right = n;
	while (right - left &gt; 1){
		int mid = (int)(left+right)/2;
		if (arr[mid] == value) return mid;
		else if (arr[mid] < value) left = mid;
		else right = mid;
	}
	if (abs(value - arr[right]) < abs(value - arr[left])) return right;
	else return left;
}

That’s it !

Categories: Algorithms, Job Tags: