两种全排列（有重复数与无重复数）的递归实现

傷城~ 2021-11-11 10:12 213阅读 0赞

1.无重复数，例子：abc，输出：abc\\acb\\bac\\bca\\cab\\cba。

分析：顺序每次取一个字母作为第一个字符，后面的子字符串重复这个过程，典型的递归。

2.有重复数，例子：abb，输出：abb\\bab\\bba

分析：加一个判断能否交换的函数isSwap()，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求\[i,j)中没有与第j个数相等的数。

代码：

package bytedance.bytedance;
    import java.util.Arrays;
    import java.util.Collections;
    //有重复数的全排列，无重复的可以直接改过去，去掉isSwap方法即可
    public class AllSort {
        public static void permutation(char[] s,int from,int to) {
            if(to <= 1)
                return;
            if(from == to) {
                System.out.println(s);
            } else {
                for(int i=from; i<=to; i++) {
                if(isSwap(s,from,i)){//顺序非常重要
                    swap(s,i,from); //交换前缀，使其产生下一个前缀
                    permutation(s, from+1, to);
                    swap(s,from,i); //将前缀换回，继续做上一个前缀的排列
                }
                }
            }
        }
        public static void swap(char[] s,int i,int j) {
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
        public static void main(String[] args) {
            char[] s = {'c','b','b','c'};
            permutation(s, 0, 3);
        }
        private static boolean isSwap(char[] s,int i,int j){
            for (int k = i; k <j ; k++) {
                if (s[k]==s[j]){
                    return false;
                }
            }
                return true;
        }
    }