无重复数组合

无重复数的组合问题
就是集合的所有非空子集

比如 {1,2,3}
的组合结果是
{1},{2},{3}
{1,2}{1,3}{2,3}
{1,2,3}
组合跟关键字的排列顺序无关

利用全排列算法求解
全排列算法可以求出集合所有的子集排列
所以 组合就是全排列的一个子集
1
2
3
12
13
21
23
31
32
123
132
213
231
312
321
一共是15个

取其中的长度为分别为1，2，3的递增序列就ok了
长度为1的： 1  2  3
长度为2的： 12 13 23
长度为3的： 123
因为组合是无序的，所以其他的舍弃

全排列参考
http://viking-liu.iteye.com/admin/blogs/1198952
一般的算法书上都有

package com.viking.divide;

public class Combination {
	public static void main(String[] args) {

		int[] a = { 1, 2, 3 ,4};
		System.out.println(perm(a, 0));
	}

	public static int perm(int[] a, int begin) {

		int count = 0;
		String path = "";
		for (int i = 0; i < begin - 1; i++) {
			if (a[i] > a[i + 1]) {
				return 0;
			}
			path += a[i] + " ";
		}
		if (begin > 0) {
                        // 输出有序的子集 就是组合的所有结果
			System.out.println(path + a[begin - 1]);
			count = 1;
		}
		if (begin == a.length) {
			return count;
		}

		for (int i = begin; i < a.length; i++) {
			swap(a, begin, i);
			count += perm(a, begin + 1);
			swap(a, begin, i);
		}
		return count;
	}

	public static void swap(int[] a, int begin, int end) {
		int temp = a[begin];
		a[begin] = a[end];
		a[end] = temp;
	}
}

上面这个算法的问题是求了在判断已排的序列是有有序时，从头开始，其实没有这个必要
因为每次递归都在判断，只要判断最后序列两个是否有序就ok了。
具体优化如下：

package com.viking.divide;

public class Combination {
	public static void main(String[] args) {
		int[] a = { 5, 2, 3, 4 };
		System.out.println(perm(a, 0));
	}

	public static int perm(int[] a, int begin) {
		int count = 0;	
		if (begin > 0) {
			if (begin > 1 && a[begin - 1] < a[begin - 2]) {
				//已排好数列无序
				return 0;
			}		
			for (int i = 0; i < begin; i++) {
				System.out.print(a[i] + " ");
			}
			System.out.println();
			count = 1;
		}
	
		for (int i = begin; i < a.length; i++) {
			swap(a, begin, i);
			count += perm(a, begin + 1);
			swap(a, begin, i);
		}
		return count;
	}

	public static void swap(int[] a, int begin, int end) {
		int temp = a[begin];
		a[begin] = a[end];
		a[end] = temp;
	}
}

上面的问题解决了判断序列是否有序时，减少比较次数。
但是整个全排列的交换次数很多，而且很多是没有意义的交换，
那么什么样的交换没有意义呢？
比如
3 21
3已经排好了，那么排21，2和1的交换就是没有意义的
因为组合只输出升序，无论 321 还是 312 最终都只有一个 3输出
所以要避免这种没有意义的交换

接着优化

package com.viking.divide;

public class Combination2 {
	public static void main(String[] args) {

		int[] a = { 4, 2, 3, 1 };
		System.out.println(perm(a, 0));		
	}
public static int c=0;
	public static int perm(int[] a, int begin) {
		int count = 0;
		if (begin > 0) {
			for (int i = 0; i < begin; i++) {
				System.out.print(a[i] + " ");
			}
			System.out.println();
			count = 1;
		}

		for (int i = begin; i < a.length; i++) {
			if (begin == 0 || a[begin - 1] < a[i]) {
				// 组合数没有顺序，所以用从小到大进行输出
				// 如果交换后不是升序，那么就不用交换，这样可以减少没有必要的交换
				swap(a, begin, i);
				count += perm(a, begin + 1);
				swap(a, begin, i);
			}
		}
		return count;
	}

	public static void swap(int[] a, int begin, int end) {	
		if (begin != end) {                   
			int temp = a[begin];
			a[begin] = a[end];
			a[end] = temp;
		}
	}
}

可以在每种方法中加入交换计数器c 计算组合的交换次数
最后一种的交换次数比前面两中方法的交换次数少很多

如果不是很理解，应该先理解全排列的算法
上面方法都是基于全排列算法改进的
求组合更好的方法。。。。