排列组合算法 java

排列组合问题，最简洁有效的方法则是利用递归

一、无重复数据选K个组合：

/*

* 无重复数据组合--dfs解法 

 * data为数据 re为结果， curpo为当前位置，curlen为当前结果的长度 ，K为目标长度

 *例如 data=“123456”  选3个字符组合，则调用----combByDfs(data,"",0,0,3);

*/ public static void combByDfs(String data, String re, int curpo, int curlen, final int K) { if (curlen == K) { System.out.println(re); return; } for (int i = curpo; i < data.length(); i++) { combByDfs(data, re + data.charAt(i), i + 1, curlen + 1, K); } } /*

* 含重复的时候组合 dfs。 假设数据已经有序，无序则sort。

  * data为数据 re为结果， curpo为当前位置，curlen为当前结果的长度 ，K为目标长度

 *例如 data=“123334”  选3个字符组合，则调用----combByDfs(data,"",0,0,3);

*/ public static void combByDfsWithReps(final String data, String re, int curpo, int curlen, final int K) { if (curlen == K) { System.out.println(re); return; } for (int i = curpo; i < data.length(); i++) { combByDfsWithReps(data, re + data.charAt(i), i + 1, curlen + 1, K); while (i + 1 < data.length() && data.charAt(i) == data.charAt(i + 1)) {  //仅仅比无重复多了一个while循环 i++; } } }

/*

 * 无重复数据全排列--dfs解法 

 * data为数据 re为结果， cur为当前位置

 *例如 data=“123456”  则调用----combByDfs(data,0);

 */ public static void permutation(String data, int cur) { if (cur == data.length()) { System.out.println(data); return; } for (int i = cur; i < data.length(); i++) { char tmp = data.charAt(i); String t = data.replace(tmp, data.charAt(cur)); String t2 = t.replaceFirst("" + t.charAt(cur), "" + tmp); permutation(t2, cur + 1); } }

/*

 * 含重复数据全排列--dfs解法 

 * data为数据 re为结果， cur为当前位置

 *例如 data=“123334”  则调用----combByDfs(data,0);

 */ public static void permutationWithReps(char[] data, int cur) { if (cur == data.length) { System.out.println(data); return; } char[] t = Arrays.copyOf(data, data.length); for (int i = cur; i < data.length; i++) { char tmp = t[i]; t[i] = t[cur]; t[cur] = tmp; permutationWithReps(t, cur + 1); while (i + 1 < data.length && data[i] == data[i + 1]) { i++; } } }