用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求：“4”不能在第三位，“3”与“5”不能相连。

Question

用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求：“4”不能在第三位，“3”与“5”不能相连。

Answer 1

package org.quzz.baidu;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class AppandDigitToString {

/**
* 给一个字符串的后面扩展多个1位数字，形成多个字符串的列表。要求：“4”不能在第三位，“3”与“5”不能相连。
* @param string 被扩展的字符串。
* @param digitList 扩展的数字列表，此列表中的每个数字，都试图扩展到字符串后面。
* @return 扩展子后形成的字符串列表。
*/
public static List appandDigitToString(String string,List digitList){
List resultList = new ArrayList();

//digitList已经为空，直接把string加入到结果列表中
if(digitList.size()==0){
resultList.add(string);
return resultList;
}

for(Integer digit: digitList){
//4不能在第3位
if(string.length()==2 && digit==4)
break;
//3与5不能相连
if(string.endsWith("3") && digit==5)
break;
if(string.endsWith("5") && digit==3)
break;

//把数字加到字符串后面，形成新串
String newString = string+digit;
//去掉已经加到字符串里面的数字，形成一个新的数字列表
List newDigitList = new ArrayList();
newDigitList.addAll(digitList);
newDigitList.remove(digit);
//递归调用
List newResultList = appandDigitToString(newString,newDigitList);

//添加新生成的字符串列表，但重复的字符串不加入
for(String newResult: newResultList){
if(!resultList.contains(newResult))
resultList.add(newResult);
}
}
return resultList;
}
public static void main(String[] args){
try{
List digitList = Arrays.asList(1,2,2,3,4,5);
List resultList = appandDigitToString("",digitList);
System.out.println("共"+resultList.size()+"种组合:");
for(String result:resultList){
System.out.println(result);
}
}catch(Exception e){
e.printStackTrace();
}
}
}
//实测{1,2,2}、{1,2,2,3}、{1,2,2,3,4}时候结果正确，具体自己验证一下吧。
//算法：有一个字符串，从一个数字数组里面依次取一个数字，当满足要求的时候就附加到此串
//之后，形成多个新串，对应每个新串的数字数组中要剔除已经附件过的数字，依次递归附加。