暴力递归——全排列

打印一个字符串的全部排列

比如有字符串"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);
        }
    }
}

暴力递归——全排列


上一篇:动态规划练习——寻找业务限制的尝试模型,洗咖啡


下一篇:暴力递归——打印一个字符串的全部子序列