求122345的全排列

Question

如题，有一个数组有122345六个元素，求他们的全排列，如122345,123245
要求：1）第三位不能是4  
      2）3和5不能连在一起，如122435是不可以的
      请考虑效率问题。
回溯法？？求答案。

Answer 1

回溯法package org.fantasizer.blog.test;/**
 * @author Marco Jee
 * @date  2010-11-6
 */
public class Combinationtest {
public static void main(String[] args) {
// 本题的思路是先用 1,3,4,5 进行全排列 // 后边再将另外两个 2 往里插入，并判断是否符合要求
int[] arr = { 1, 3, 4, 5 };
printcom(arr, 0);
} public static void printcom(int[] arr, int index) {
if (index == arr.length - 1) {
inserttwo(arr, 0);
return;
}
printcom(arr, index + 1);
for (int i = index + 1; i < arr.length; i++) {
arr[index] ^= arr[i];
arr[i] ^= arr[index];
arr[index] ^= arr[i];
printcom(arr, index + 1);
arr[index] ^= arr[i];
arr[i] ^= arr[index];
arr[index] ^= arr[i];
}
} 

// 将 2 在符合要求的情况下插入数组
private static void inserttwo(int[] arr, int index) {
if (index == arr.length + 1)
return;
for (int i = index + 1; i < arr.length + 2; i++) {
int[] tar = new int[arr.length + 2];
tar[i] = 2;
tar[index] = 2;
innerinsert(arr, tar);
}
inserttwo(arr, index + 1);
} private static void innerinsert(int[] arr, int[] tar) {
int index = 0;
int indexarr = 0;
while (index < tar.length) {
if (tar[index] == 0) {
if (index > 0 && tar[index - 1] + arr[indexarr] == 8
|| (index == 2 && arr[indexarr] == 4))
return;
tar[index] = arr[indexarr++];
}
index++;
}
for (int i = 0; i < tar.length; i++) {
System.out.print(tar[i] + " ");
}
System.out.println();
}
}

Answer 2

 //请问抑或的作用是什么，我算法学的不是很好。谢谢
 //希望有详尽的解释
 //我如果理解的会分就全部给你了
 for (int i = index + 1; i < arr.length; i++) {
            arr[index] ^= arr[i];
            arr[i] ^= arr[index];
            arr[index] ^= arr[i];
            printcom(arr, index + 1);
            arr[index] ^= arr[i];
            arr[i] ^= arr[index];
            arr[index] ^= arr[i];
        }