打印一个字符串的全部排列
比如有字符串"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); } } }