算法

Question

122345，其中第三位不能是3，2与2不能相邻，然后将所有可能得的情况输出。怎么编写

Answer 1

简单的思路就是全排列，然后把不符合条件的数据过滤
public class Sample {
public static void main(String[] args) {
try {
int[] src = new int[] {1,2,2,3,4,5};
List<List<Integer>> buf = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
for (int n : src) {
if (result.size() == 0) {
result.add(new ArrayList<>(Arrays.asList(new Integer[] {n})));
continue;
} else {
buf.clear();
while (result.size() > 0) {
List<Integer> l = result.remove(0);
if (l.indexOf(2) == l.lastIndexOf(2)-1) { //过滤2相邻
continue;
}
int idx = 0, end = l.size();
if (l.size() == src.length-1) { //最后一个排列数字的时候
if (l.indexOf(3) == 1) { // 如果位置2是3的话，只能插在3以后的位置
idx = l.indexOf(3) + 1;
} else if (l.indexOf(3) == 2) { //如果位置3为3的话，只能插在3以前的位置
end = 2;
}
}
for (int i=idx; i<end; i++) { 
List<Integer> tmp = new ArrayList<Integer>(l);
tmp.add(i, n); //把数字插入中间不同的位置
buf.add(tmp);
}
if (end == l.size()) {
List<Integer> tmp = new ArrayList<Integer>(l);
tmp.add(n);  //把数字插入最后一个位置
buf.add(tmp);
}
}
result.addAll(buf);
}
}
buf.clear();
buf.addAll(result);
result.clear();
for (int i=0; i<buf.size(); i++) {
boolean b = false;
for (int j=0; j<result.size(); j++) { //因为有2个2，所以排列出现重复，过滤掉重复的数据
if (buf.get(i).toString().equals(result.get(j).toString())) {
b = true;
break;
}
}
if (! b) {
result.add(buf.get(i));
}
}

for (int i=0; i<result.size(); i++) {
System.out.println(result.get(i));
}
System.out.println(result.size());
} catch (Throwable e) {
e.printStackTrace();
}
}
}