全排列——DFS实现

原创

之间就写过一篇全排列的博客：https://www.cnblogs.com/chiweiming/p/8727164.html

详细介绍请回看，用的方法（暂且就叫）是“交换法”，其实思路就是DFS（深度优先搜索），此篇博客对上次全排列思想进行一次升华。

例子：

有3个盒子 1、2、3，3张扑克牌 1、2、3，进行扑克牌全排列可以这样实现：

不管面对哪个盒子，都尝试按“1--n”的顺序将扑克牌放入，如果第m张扑克牌已经用过，判断第m+1张是否可用。

当放满n个盒子时，回头，把盒子里面的牌捡回来，再继续按顺序放牌进盒子。

过程：

第1个盒子：放入1号牌

第2个盒子：本来应该放入1号牌，但是由于1号牌已用，只能按顺序放入2号牌

第3个盒子：本来应该放入1号牌，但是1号牌已用，而且判断2号牌也已用，只能放入3号牌

盒子放满，输出

回头，捡回第3个盒子的牌；

第3个盒子：由于手里只有3号牌，放不了了，只能再回头

第2个盒子：捡回2号牌，此时手里剩2、3号牌，对于第2个盒子，按顺序放牌、现在可以将3号牌放入。

第3个盒子：重新按“1--n”的顺序放牌，所以放入2号牌

回头......

（其实本人第一篇的全排列博客也是用了DFS，每个位置都按顺序放入数字）

（DFS的思想：这一步的选择和下一步的选择相同，进入下一步只需像上层操作即可）

 import java.util.Scanner;

 public class FullSort {

     static int n;

     static int total=0;

     static int box[];    //装入牌

     static int pai[];    //pai[m]=1代表第m张牌已用，=0代表未用

     public static void full_Sort(int step) {    //step代表第step个盒子

         if(step==n+1) {

             for(int i=1;i<=n;i++) {

                 System.out.print(box[i]+" ");

             }

             System.out.println();

             total++;

             return;

         }

         for(int i=1;i<=n;i++) {    //每个盒子都尝试按“顺序”放入1~n张牌

             if(pai[i]==0) {    //第i张牌没用

                 box[step]=i;

                 pai[i]=1;

                 full_Sort(step+1);

                 pai[i]=0;    //回溯

             }

         }

     }

     public static void main(String[] args){

         Scanner reader=new Scanner(System.in);

         n=reader.nextInt();    //1~n张扑克牌

         box=new int[n+1];

         pai=new int[n+1];

         for(int i=1;i<=n;i++) {    //每张牌都未用

             pai[i]=0;

         }

         full_Sort(1);

         System.out.println("一共有"+total+"种排列");

     }

 }

全排列

13:37:24

2018-07-08

巴特西

全排列——DFS实现

最新文章

热门文章