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;
}
}
}
}这个排序我不懂,谁能帮我分析下,有劳啦。

解决方案 »

  1.   

    找由6个数字组成的组合,每个组合6个位置(从左道右排列,最左为第一位,最右为最后一位)
    总共会有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位数字组合。
      

  2.   

    补充:最开始调用的find()不算是main()方法中调用的find()