題目例如以下：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].

---

分析：假設僅僅是求排列數(shù)非常好算，可是要打印全部排列且不反復比較困難。

假設單純用for循環(huán)或遞歸。非常easy出現(xiàn)死循環(huán)。

而假設用隨機生成排列，直到打印出全部排列。又easy超時。

? ??? ? 因此通過對問題的分析，發(fā)現(xiàn)能夠將原問題映射成為n皇后問題。每一次排列映射為n皇后的一次成功擺放，打印全部的排列即打印全部擺放皇后的方法。但與n皇后問題不同的是。此問題皇后不能放在同行同列，卻能夠放在對角線。因此核心還是回溯法，代碼例如以下：
import?java.util.ArrayList;
import?java.util.Stack;
public?class?Main?{
????public?static?void?main(String[]?args)
????{
????????int[]?num={1};
????????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>();
????????if(num.length==0)
????????????return?result;
????????if(num.length==1)
????????{
????????????elem.add(num[0]);
????????????result.add(elem);
????????????return?result;
????????}
????????int?row;
????????QueuePos.push(0);
????????row=0;
????????while(row>=0)
????????{
????????????put_queue(QueuePos,row,QueueNum);
????????????//皇后放置完成
????????????for(int?i=0;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=QueueNum-2;
????????QueuePos.pop();
????????column=QueuePos.pop();
????????column=column+1;
????????while(row>=0)
????????{
????????????
????????????if(column<QueueNum&&!QueuePos.contains(column))
????????????{
????????????????QueuePos.push(column);
????????????????return?row;
????????????}
????????????else?if(column==QueueNum)
????????????{
????????????????row--;
????????????????if(row<0)
????????????????????return?row;
????????????????column=QueuePos.pop();
????????????????column=column+1;
????????????}else
????????????{
????????????????column++;
????????????}
????????}
????????return?row;
????}
????
????public?static?boolean?put_queue(Stack<Integer>?QueuePos,int?row,int?QueueNum)
????{
????????int?i,j,column;?//i代表行。j代表列
????????i=row+1;
????????while(i<QueueNum)
????????{
????????????for(j=0;j<QueueNum;j++)
????????????????if(!QueuePos.contains(j))
????????????????????break;
????????????if(j!=QueueNum)
????????????{
????????????????QueuePos.push(j);
????????????????i++;
????????????????j=0;
????????????}
????????????else
????????????{
????????????????i--;
????????????????if(i>=0)
????????????????{
????????????????????column=QueuePos.pop();
????????????????????QueuePos.push(column+1);
????????????????}else
????????????????????return?false;
????????????}
????????}
????????return?true;
????}
}

版權聲明：本文博主原創(chuàng)文章。博客，未經同意不得轉載。

轉載于:https://www.cnblogs.com/zfyouxi/p/4828498.html

總結

以上是生活随笔為你收集整理的打印到类阵列的给定序列的所有排列的n皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。