考古学家--二星

• 有一个考古学家发现了一个石碑，但是很可惜，发现时其已经断裂成n断，原地发现n个断口整齐的碎片
• 为了破解石碑内容，考古学家需要计算石碑文字组合数，
• 输入描述
• 第一行：输入n，表示n个碎片
• 第二行：输入文字的内容，共n组，用空格分开，由于模拟石碑的碎片，所以不用考虑重复字符
• 如： 3
• a b c
• 输出描述：
• 输出所有的排列组合
• 如：abc acb bca bac cab cba

import java.util.Stack;
public class Question38 {
    public static void main(String[] args) {
        //测试用例，实际可用Scanner进行测试
        char[] arr = new char[]{'a', 'b', 'c', 'd'};
        answer(arr);
    }
    public static void answer(char[] arr){
        //分析：如果是一个，则只有一个排列，如果是两个，则将第二个字符插入第一个的前两个位置，以此类推
        Stack<String> stack1 = new Stack<>();
        Stack<String> stack2 = new Stack<>();
        stack1.add(arr[0] + "");
        for (int i = 1; i < arr.length; i++) {
		  //此处可以优化一下，不用每次都从stack1开始，只要保证有一个为空就好了，这里懒的改了，有兴趣的小伙伴自己尝试
            while (!stack1.isEmpty()){
                String tempS = stack1.pop();
                for (int j = 0; j <= tempS.length(); j++) {
                    String s = tempS.substring(0, j) + arr[i] + tempS.substring(j);
                    stack2.add(s);
                }
            }
            while (!stack2.isEmpty()){
                stack1.add(stack2.pop());
            }
        }
        while (!stack1.isEmpty()){
            System.out.println(stack1.pop());
        }
    }
}