package yudylaw.java.sorted;import java.util.ArrayList;import java.util.List;
import java.util.Set;
import java.util.TreeSet;/**
* 输出1,2,2,3,4,5的所有排列组合,4不能在第三位,3和5不能相邻
*
* 采用字符跟踪
* @author ****
* 10:56:38 PM Apr 23, 2009
*/
public class Sorted {
public static List<String> find(List<String> list) {
List<String> rtn = new ArrayList<String>();
String str;
for (int i = 0; i < list.size(); i++) {
str = list.get(i);
list.remove(i);
if (list.size() == 0) {
rtn.add(str);
} else {
List<String> sList = find(list);
for (String s : sList) {
rtn.add(str + s);
if (s.length() == 5) {
addNumber(str + s);
}
}
}
list.add(i, str);
}
return rtn;
} /**
* 通过这个来排除
* @param str
*/
public static void addNumber(String str) {
if (str.charAt(2) == '4' || str.contains("35") || str.contains("53")) {
return;
}
set.add(str);
} public static Set<String> set = new TreeSet<String>(); public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
find(list);
System.out.println(set.size());
int cols = 10;
for (String s : set) {
System.out.print(s + " ");
if (cols-- == 1) {
System.out.println();
cols = 10;
}
}
}
}这个排序我不懂,谁能帮我分析下,有劳啦。
总共会有6层递归。
规定最开始调用的find()为最底层,也就是第一层。
设层数为n,从1开始到6,
(就单次连续的提取数字来说,n层循环次数为6-n+1次。)
每次循环分别从保留下来的数字字符中取出一个。
取出的一个字符相当于在这6个数字中选取一个放入待组合的第n位上。
又如下:
一层,二层,三,四,五取1 , 取2 ,2 , 3, 4, 5 >> 到第五层获得"45"
以此类推
1,2,2,3,5,4 >> "54"
1,2,2,4,3,5 >> "35"
1,2,2,4,5,3 >> "53"
1,2,2,5,3,4 >> "34"
1,2,2,5,4,3 >> "43"可见,下层down所有的find()执行完返回上层up一个集合,该集合包含down层针对up以及up前的取数方式所剩下数字的组合方式。只在第一层,也就是返回集合元素长度为5时才调用了addNumber(),组合成复合要求的6位数字组合。