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

比如 {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 计算组合的交换次数
最后一种的交换次数比前面两中方法的交换次数少很多

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