求全排列和非空子集算法——排列组合

野性酷女 2021-09-28 19:44 399阅读 0赞

在数学种排列和组合都是很重要的，在算法中也是，下面我们将介绍几种求全排列和求元素所有子集的方法。

**一、全排列**

全排列如果使用递归来实现的话是元素与元素交换的问题，而如果使用迭代实现的话是把当前字符加在已形成字符的前面或后面的问题。这里分别使用迭代，普通递归和多路递归+回溯实现。

**迭代实现**

//迭代实现,子问题:加在前面,加在后面,加在中间
        static List<String> getPermutation(String s)  {
            List<String> res = new ArrayList<>();
            res.add(s.charAt(0)+"");
            
            for(int i=1;i<s.length();i++) {
                List<String> res_new = new  ArrayList<>();
                char c = s.charAt(i);
                for(String e:res) {
                    String str = c + e;
                    res_new.add(str);//加在前面
                    str = e + c;
                    res_new.add(str);//加在后面
                    for(int j=1;j<e.length();j++) {
                        str =  e.substring(0,j)+c+e.substring(j);
                        res_new.add(str);
                    }
                    res = res_new;
                }
            }
            System.out.println(res.size());
            return res;
        }

**递归实现**

/**
         * 递归求全排列,子问题
         * @param s
         * @param k 指定字符串子中字符的指针，一般为0
         * @return
         */
        static List<String> getPermutation1(String  s,int k) {
            List<String> res_new = new  ArrayList<>();
            if(k == 0) {
                char ch = s.charAt(0);
                res_new.add(ch+"");
                return res_new;
            }
            List<String> res_old =  getPermutation1(s,k-1);
            
            char c =  s.charAt(k);
            for(String e : res_old) {
                String str = c + e;
                res_new.add(str);
                str = e + c;
                res_new.add(str);
                
                for(int i=1;i<e.length();i++) {
                    str =  e.substring(0,i)+c+e.substring(i);
                    res_new.add(str);
                }
            }
            return res_new;
        }

**多路递归+回溯实现**

/**
         * 多路递归+回溯
         * @param A 字符数组
         * @param k 当前元素下标
         */
        static void getPermutation2(char[] A, int k)  {
            if(k==A.length-1) {
                for (char c : A) {
                    System.out.print(c);
                }
                System.out.println();
                return;
            }
            
            for(int i=k;i<A.length;i++) {
                swap(A,i,k);//把后面的每个字符换到k位
                getPermutation2(A,k+1);
                swap(A,i,k);//回溯
            }
        }
        
        static void swap(char[] arr,int x,int y) {
            char tem = arr[x];
            arr[x] = arr[y];
            arr[y] = tem;
        }

二、求（非空）子集

求子集是一个集合要此元素或者不要此元素的问题。可以通过迭代、递归或者二进制实现。

**注意：**起始应该有一个空集，这个空集是子集的开始状态，如果没有空集合，即只从一个元素的集合开始，此时仅会在一个元素的基础上进行添加/不添加操作，因此会少其他单个元素。

**迭代实现**

/**
         * 迭代实现
         * @param arr
         */
        static Set<Set<Integer>> subset(int[] arr){
            Set<Set<Integer>> res = new HashSet<>();
            res.add(new HashSet<>());//初始化位空集
            for(int i=0;i<arr.length;i++) {
                Set<Set<Integer>> newSet = new  HashSet<>();
                newSet.addAll(res);
                for(Set<Integer> set:res) {
                    Set<Integer> clone =  (Set<Integer>)((HashSet)set).clone();
                    clone.add(arr[i]);
                    newSet.add(clone);
                }
                res = newSet;
            }
            return res;
        }

**递归实现**

/**
         * 递归实现
         * @param arr
         * @param cur arr数组最大下标
         * @return
         */
        static Set<Set<Integer>> subset(int[]  arr,int cur) {
            Set<Set<Integer>> newSet = new  HashSet<>();
            if(cur == 0) {//出口一一定要放在方法的前部分
                Set<Integer> nullSet = new  HashSet<>();
                Set<Integer> fir_element = new  HashSet<>();
                fir_element.add(arr[0]);
                newSet.add(nullSet);
                newSet.add(fir_element);
                return newSet;
            }
            Set<Set<Integer>> oldSet =  subset(arr,cur-1);
            for(Set<Integer> set : oldSet) {
                //备份集合
                Set<Integer> clone =  (Set<Integer>)((HashSet)set).clone();
                newSet.add(set);//添加无元素的集合
                clone.add(arr[cur]);//在备份集合中添加元素
                newSet.add(clone);//添加有元素集合
            }
            return newSet;
        }

**二进制实现**

/**
         * 二进制位实现
         * @param A
         * @return
         */
        static Set<Set<Integer>> subset(int[] A){
            char[][] bin_arr = new  char[(int)Math.pow(2, A.length)][];
            for(int i=0;i<bin_arr.length;i++) {
                bin_arr[i] = new  StringBuilder(Integer.toString(i,2)).reverse().toString().toCharArray();
            }
            Set<Set<Integer>> res = new HashSet<>();
            for(int i=0;i<bin_arr.length;i++) {
                Set<Integer> tem = new HashSet<>();
                for(int j=0;j<bin_arr[i].length;j++)  {
                    if(bin_arr[i][j] ==  '1')tem.add(A[j]);
                }
                res.add(tem);
                tem = null;//回收tem指向的HashSet对象;
            }
            return res;
        }