subset.java

PKU中一些数据结构基本算法题的java实现

package OTHERS;

public class SubSet {
	char[] chs;
	int bits = 0;

	public SubSet(char[] chs) {
		this.chs = chs;
	}

	public void Print() {
		for (int i = 0; i < (1 << chs.length); i++) {
			for (int j = 0; j < chs.length; j++) {
				if (((1 << j) & i) != 0) {
					System.out.print(chs[j]);
				}
			}
			System.out.println();
		}
	}

	
	public void printK(int[] a, int k, int n, int level){

		int[] m = a.clone();
		if (n - k < level) {
			return;
		}
		else if(level==0){
			for (int i = 0; i < k; i++) {
				if (a[i] != 0) {
					System.out.print(a[i]);
				}
			}
			System.out.println();
			return;
		}
		else if(k == n) {
			for (int i = 0; i <= n - 1; i++) {
				if (a[i] != 0) {
					System.out.print(a[i]);
				}
			}
			System.out.println();
			return;
		} else {
			printK(m,k+1,n,level-1);
			m[k]=0;
			printK(m,k+1,n, level);
			
		}
	}
	
	public void f(int[] a, int k, int n, int currentSelectedNum,
			int currentDropNum, int level) {
		int[] m = a.clone();
		if (currentSelectedNum > level) {
			return;
		}
		if (n - currentDropNum < level) {
			return;
		}
		if (k == n) {
			for (int i = 0; i <= n - 1; i++) {
				if (a[i] != 0) {
					System.out.print(a[i]);
				}
			}
			System.out.println();
		} else {
			f(m, k + 1, n, currentSelectedNum + 1, currentDropNum, level);
			m[k] = 0;
			f(m, k + 1, n, currentSelectedNum, currentDropNum + 1, level);
		}
	}

	public static void main(String[] args) {
		char[] chs = { 'a', 'b' };
		int[] set = { 1, 2, 3, 4 };
		SubSet s = new SubSet(chs);
		//s.f(set, 0, 4, 0, 0, 3);
		s.printK(set, 0, 4, 3);
		// s.Print();
	}

}