打印一个字符串的全部排列
比如有字符串"abc"，这个字符串的全排列有哪些呢，相信大家高中肯定有学过，如果忘了也不要紧，我来给大家回忆一下，很简单的😄，请看下图，记住一个原则，已经做过决策了的位置不用重复做决策！！！
// str[0...i-1] str数组0~i-1位置已经已经做好了决定，不用再做决定！！！ // str[i...] str数组i位置及其以后的位置都有机会来到i位置 // i来到终止位置后，str当前的样子就是一种结果，放入ans中 public static void process1(char[] str,int i,ArrayList<String> ans) { if(i==str.length) { ans.add(String.valueOf(str[i])); return ; } // i没有来到终止位置，i及其往后的位置都可以来到i位置 for(int j=i; j<str.length; j++) { swap(str, i, j); process1(str, i+1, ans); // 恢复现场 swap(str, j, i); } } public static void swap(char[] chs,int i,int j) { char tmp=chs[i]; chs[i]=chs[j]; chs[j]=tmp; } public static List<String> printAllPermutations(String s){ char[] str=s.toCharArray(); ArrayList<String> ans=new ArrayList<>(); if(s==null || s.length()==0) { return ans; } process1(str, 0, ans); return ans; }
现在题目升级，
打印一个字符串的全部排列，要求不要出现重复的排列
方法一：全部打印出来再去重，推荐看看上篇文章——暴力递归——打印一个字符串的全部子序列。因为方法很类似，就不具体说了。
方法二：分支限界，一种提前杀死支路的暴力递归，跟方法一相比优化了不少。
核心代码：
public static void process2(char[] str,int i,ArrayList<String> ans) { if(i==str.length) { ans.add(String.valueOf(str)); return ; } boolean[] visited=new boolean[26]; for(int j=i; j<str.length; j++) { if(!visited[str[j]-'a']) { visited[str[j]-'a']=true; swap(str, i, j); process2(str, i+1, ans); swap(str, j, i); } } }
完整代码：
package com.harrison.class12; import java.util.ArrayList; import java.util.List; public class Code04_PrintAllPermutatioins { // str[0...i-1] str数组0~i-1位置已经已经做好了决定，不用再做决定！！！ // str[i...] str数组i位置及其以后的位置都有机会来到i位置 // i来到终止位置后，str当前的样子就是一种结果，放入ans中 public static void process1(char[] str,int i,ArrayList<String> ans) { if(i==str.length) { ans.add(String.valueOf(str)); return ; } // i没有来到终止位置，i及其往后的位置都可以来到i位置 for(int j=i; j<str.length; j++) { swap(str, i, j); process1(str, i+1, ans); // 恢复现场 swap(str, j, i); } } public static void swap(char[] chs,int i,int j) { char tmp=chs[i]; chs[i]=chs[j]; chs[j]=tmp; } public static List<String> printAllPermutations(String s){ char[] str=s.toCharArray(); ArrayList<String> ans=new ArrayList<>(); if(s==null || s.length()==0) { return ans; } process1(str, 0, ans); return ans; } public static void process2(char[] str,int i,ArrayList<String> ans) { if(i==str.length) { ans.add(String.valueOf(str)); return ; } boolean[] visited=new boolean[26]; for(int j=i; j<str.length; j++) { if(!visited[str[j]-'a']) { visited[str[j]-'a']=true; swap(str, i, j); process2(str, i+1, ans); swap(str, j, i); } } } public static List<String> printNoRepeat(String s){ char[] str=s.toCharArray(); ArrayList<String> ans=new ArrayList<>(); if(s==null || s.length()==0) { return ans; } process2(str, 0, ans); return ans; } public static void main(String[] args) { String test="acc"; List<String> ans1=printAllPermutations(test); List<String> ans2=printNoRepeat(test); for(String cur: ans1) { System.out.println(cur); } System.out.println("==================="); for(String cur: ans2) { System.out.println(cur); } } }
