字符串的全排列问题的解决方法

痛定思痛。 2022-06-08 14:06 169阅读 0赞

package exampletest;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    public class Main01 {
    
        public static void main(String[] args) {
            String str = "ABCD";
            ArrayList<String> list = new ArrayList<>();
            Permutation(list,str.toCharArray(),0);
            System.out.println(list);
        }
    
        /**
         * 字符串全排列问题:ABC
         * 如果能生成n-1个元素的全排列，则能生成n个元素的全排列。
         * 1）固定第一个字符A，求后面两个字符BC的排列；
         * 2）当两个字符BC排列好后，把第一个字符A和B交换，得到BAC，接着固定第一个字符B，求后面AC的排列。
         * 3）现在把C放在第一个位置，由于前面已经交换了AB，为了保证这次C仍是和原先处在第一个位置的A交换，
         * 在交换C之前，先要把B和A交换回来。在交换B和A之后，再拿C和处于第一位置的A进行交换，得到CBA。
         * 再次固定第一个字符C，求后面两个字符B、A的排列。
         * @param list
         * @param ch
         * @param n
         */
        public static void Permutation(ArrayList<String> list ,char[] ch ,int n){
             if (n == ch.length){
                 //交换一次完成记录
                 list.add(new String(ch));
             }
            for (int i = n; i < ch.length; i++) {
                //交换字符串长度的次数
                swap(ch,i,n);//交换后面的 步骤2）
                Permutation(list,ch,n+1);
                swap(ch,i,n);//交换前面的 步骤3）
            }
    
        }
    
        /**
         * 交换字符
         * @param ch
         * @param i
         * @param j
         */
        public static void swap(char[] ch,int i,int j){
            if (i != j){
                char c = ch[i];
                ch[i] = ch[j];
                ch[j] = c;
            }
        }
    }