n的全排列（栈和递归）

Description 给你一个数n，请你列出1，2，3，4…n-1，n的全排列。

Input 输入一个数n Ouput 输出相应的全排列 Sample Input

3

Sample Output

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

算法思路： 先将1 - n依次压入栈中，这是第一组排列，输出；接着循环while(!st.isEmpty()) 每次弹出栈顶元素，然后找在栈外的数有没有比弹出的这个数更大的，如果有那个将这个大的数压入栈中，接着从1-n查找不在栈中的数，依次压入栈中，一次排列输出，结束

这里模拟下3的全排列 out->1 2 3 （1，2）3出栈，（1）3出栈，2出栈，（1，3入栈）2，（1，3，2入栈） out->1 3 2 (1，3) 2出栈， （1）2出栈，3出栈，（）2出栈，3出栈，1出栈 （2入栈）3，1 （2，1入栈）3 （2，1，3入栈） out->2 1 3 (2，1)3出栈 （2）3出栈，1出栈 （2，3入栈）1 （2，3，1入栈） out->2 3 1 (2，3) 1出栈 （2）1 出栈，3出栈 （）1出栈，3出栈，2出栈 （3入栈）1，2 （3，1入栈）2 （3，1，2入栈) out->3 1 2 (3，1) 2出栈 （3）2出栈，1出栈 （3，2入栈）1 （3，2，1入栈） out->3 2 1

用栈的代码：

import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); Stack<Integer> st = new Stack<Integer>(); for(int i=1;i<=n;i++){ st.push(i); } System.out.println(st.toString()); while(!st.isEmpty()){ int i = st.pop(); //System.out.println(i); for(;i<n;i++){ /* * st.search(x) 查找栈中有没有这个数，如果有返回它距离栈顶的距离 * 否则返回-1 */ if(st.search(i+1)<0){ st.push(i+1); //将大于弹出的这个数入栈 //接着将未入栈的从小到大依次入栈 for(int j=1;j<=n;j++){ if(st.search(j)<0){ st.push(j); } } //全部入栈排完了一组，输出结束 System.out.println(st.toString()); break; } } } } } }

递归

import java.util.Scanner; public class Main { static int n; //对1-n进行全排 static int flat[]; //做标记 static int p[]; //存放排好的数 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = 1; while(sc.hasNext()){ n = sc.nextInt(); flat = new int[n]; p = new int[n]; System.out.println("Case "+count+++":"); DFS(0); } } public static void DFS(int step){ //第step步开始 if(step==n){ //出口 System.out.print("["+p[0]); for(int i=1;i<n;i++){ System.out.print(", "+p[i]); } System.out.println("]"); }else{ for(int i=0;i<n;i++){ if(flat[i]==0){ //第i个数没用过 p[step] = i+1; //第step放i+1 flat[i] = 1; //标记为用过 DFS(step+1); //接着排下一个位置 flat[i] = 0; //排完后清除标记，回溯 } } } } }