题目例如以下：Given
a collection of numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],
and [3,2,1].
分析：假设仅仅是求排列数非常好算，可是要打印全部排列且不反复比較困难。
假设单纯用for循环或递归。非常easy出现死循环。
而假设用随机生成排列，直到打印出全部排列。又easy超时。
因此通过对问题的分析，发现能够将原问题映射成为n皇后问题。每一次排列映射为n皇后的一次成功摆放，打印全部的排列即打印全部摆放皇后的方法。但与n皇后问题不同的是。此问题皇后不能放在同行同列，却能够放在对角线。因此核心还是回溯法，代码例如以下：
import java.util.ArrayList;
import java.util.Stack;
public class Main {
public static void main(String[] args)
{
};
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
result=permute(num);
System.out.print(result);
}
public static ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> elem=new ArrayList<Integer>();
int QueueNum=num.length;
Stack<Integer> QueuePos=new Stack<Integer>();
)
return result;
)
{
elem.add(num[]);
result.add(elem);
return result;
}
int row;
QueuePos.push();
row;
)
{
put_queue(QueuePos,row,QueueNum);
//皇后放置完成
;i<QueuePos.size();i++)
{
elem.add(num[QueuePos.get(i)]);
}
result.add(elem);
elem=new ArrayList<Integer>();
//寻找下一个方法
row=find_next(QueuePos,QueueNum);
//status=put_queue(QueuePos,row,QueueNum);
}
return result;
}
public static int find_next(Stack<Integer> QueuePos,int QueueNum)
{
int row,column;
row;
QueuePos.pop();
column=QueuePos.pop();
column;
)
{
if(column<QueueNum&&!QueuePos.contains(column))
{
QueuePos.push(column);
return row;
}
else if(column==QueueNum)
{
row--;
)
return row;
column=QueuePos.pop();
column;
}else
{
column++;
}
}
return row;
}
public static boolean put_queue(Stack<Integer> QueuePos,int row,int QueueNum)
{
int i,j,column; //i代表行。j代表列
i;
while(i<QueueNum)
{
;j<QueueNum;j++)
if(!QueuePos.contains(j))
break;
if(j!=QueueNum)
{
QueuePos.push(j);
i++;
j;
}
else
{
i--;
)
{
column=QueuePos.pop();
QueuePos.push(column);
}else
return false;
}
}
return true;
}
}
版权声明：本文博主原创文章。博客，未经同意不得转载。