java求集合的所有子集、所有子序列、全排列全组合问题

1.求集合的所有子集（又称全组合）

求一个集合的所有组合，例如集合{A,B,C}的所有子集为：{},{A,B,C},{A,B},{A,C},{B,C},{A},{B},{C}。

思路

对于任意集合A，元素个数为n（空集n=0），则所有子集的个数为2^n个

如集合A={a,b,c},其子集个数为8；对于任意一个元素，在每个子集中，

要么存在，要么不存在，对应关系是：

a=1或a=0，b=1或b=0，c=1或c=0

映射为子集：

(1,1,1)->(a,b,c)

(1,1,0)->(a,b  )

(1,0,1)->(a,  c)

(1,0,0)->(a     )   

(0,1,1)->(  b,c)

(0,1,0)->(  b   )

(0,0,1)->(     c)

(0,0,0)->( )  空集

观察以上规律，与计算机中数据存储方式相似，故可以通过(a=100,b=010,c=001)与集合映射000 – 111（0表示有，1表示无）作与运算，即获取集合的相应子集。

算法1：

位图法：

1）构造一个和集合一样大小的数组A，分别与集合中的某个元素对应，数组A中的元素只有两种状态：“1”和“0”，分别代表每次子集输出中集合中对应元素是否要输出，这样数组A可以看作是原集合的一个标记位图。

2）数组A模拟整数“加一”的操作，每“加一”之后，就将原集合中所有与数组A中值为“1”的相对应的元素输出。

代码如下

    /**
     * 获取所有子集
     */
    private static ArrayList<ArrayList<Integer>> getSubList(int[] arr) {
        ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
        int size = 1 << arr.length;// 2^n次方
        for (int mark = 0; mark < size; mark++) {
            ArrayList<Integer> aList = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                /* 重要：这句是最重要的代码:是 0-7 分别与运算 1，2，4
                 * 000 001 010 011 100 101 110 111
                 * 
                 */
                if ((mark & (1 << i)) != 0) {
                    aList.add(arr[i]);
                }
            }
            allList.add(aList);
        }
        return allList;
    }

    public static void main(String[] args) {
        int[] arr= {1,2,3};
        ArrayList<ArrayList<Integer>> list = getSubList(arr);
        for (int i=0;i<list.size();i++) {
            ArrayList<Integer> mList=list.get(i);
            for (int j=0;j<mList.size();j++) {
                System.out.print(mList.get(j)+" ");
            }
            //换行
            System.out.println();
            
        }
    }

算法2：递归迭代法：

public class Demo {
 
    public static void main(String[] args) {
        int[] arr = {1, 2};
        Set<Set<Integer>> f = f(arr.length, arr);
        System.out.println(f);
    }
 
    public static Set<Set<Integer>> f(int k, int[] arr) {
        if (k == 0) {
            Set<Set<Integer>> set = new HashSet<>();
            set.add(new HashSet<>());//添加一个空集合
            return set;
        }
 
        Set<Set<Integer>> set = f(k - 1, arr);
        Set<Set<Integer>> resultSet = new HashSet<>();
 
        for (Set<Integer> integerSet : set) {//扫描上一层的集合
 
            //上一层的每个集合都包含两种情况，一种是加入新来的元素，另一种是不加入新的元素
            HashSet<Integer> subSet = new HashSet<>();
 
            subSet.addAll(integerSet);
            subSet.add(arr[k - 1]);
 
            resultSet.add(subSet);
            resultSet.add(integerSet);
        }
        return resultSet;
    }
}

2.求集合的所有排列（又称全排列）

一，问题描述

给定一个字符串，求出该字符串的全排列。

比如：”abc”的全排列是：abc、acb、bac、bca、cab、cba

二，实现思路

* 从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，
* 从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例：
* 固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
* 固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
* 固定c，求后面ba的排列：cba，cab。
* 
* 即递归树：
　　　　　str:　a 　　　　 b 　　　　　 c
　　　　　　　ab ac 　　 ba bc 　　　ca cb
　　      result:  abc acb 　bac bca　    cab cba

    /*
     * 全排列
     */
    public static void permutation(String str, String result) {
        /* 全排列 递归实现 
                          递归树：
          str:          a            b                c
                      ab ac         ba   bc         ca   cb
        result:        abc acb        bac    bca      cab   cba
         */

        // 当result长度等于长度，说明已经遍历到叶子节点，直接打印
        if (result.length() == str.length()) { // 表示遍历完了一个全排列结果
            System.out.println(result);
        } else {
            for (int i = 0; i < str.length(); i++) {
                // 判断result中没有 a、b、c
                if (result.indexOf(str.charAt(i)) < 0) { 
                    permutation(str, result + str.charAt(i));
                }
            }
        }
    }

    public static void main(String args[]) throws Exception { 
         String str="abc";
         permutation(str,"");
    }

3.求集合的所有子序列（即所有的排列组合）

思路：

子序列和子集合不一样，子序列有顺序差别，子集合没有顺序，子序列为所有子集合的排列组合，即集合的所有子序列 = 集合的所有子集合的排列组合集。

    /*
     * 获取所有子集(全组合)
     */
    private static List<String> combination(String str) {
        ArrayList<String> allList = new ArrayList<>();
        int size = 1 << str.length();// 2^n次方
        for (int mark = 0; mark < size; mark++) {
            ArrayList<String> aList = new ArrayList<>();
            for (int i = 0; i < str.length(); i++) {
                /* 重要：这句是最重要的代码:是 0-7 分别与运算 1，2，4
                 * 000 001 010 011 100 101 110 111
                 * 
                 */
                if ((mark & (1 << i)) != 0) {
                    aList.add(str.charAt(i)+"");
                }
            }
            allList.add(String.join("", aList));
        }
        //allList.forEach((item)->{System.out.println(item);});
        return allList;
    }

    /*
     * 全排列
     */
    public static void permutation(String str, String result, List<String> allResult) {
        /* 全排列 递归实现 
                          递归树：
          str:          a            b                c
                      ab ac         ba   bc         ca   cb
        result:        abc acb        bac    bca      cab   cba
         */
        
        // 结果 开始传入"" 空字符进入 len 是这个数的长度
        if (result.length() == str.length()) { 
            // 表示遍历完了一个全排列结果
            allResult.add(result);
        } else {
            for (int i = 0; i < str.length(); i++) {
             // 返回指定字符在此字符串中第一次出现处的索引。
                if (result.indexOf(str.charAt(i)) < 0) { 
                    permutation(str, result + str.charAt(i), allResult);
                }
            }
        }
    }

    public static void main(String[] args) {
        
        String str="abc";
        List<String> allList = combination(str);
        List<String> allSequence = new ArrayList<>();
        allList.forEach((item)->{
            List<String> sequence = new ArrayList<>();
            permutation(item,"",sequence);
            allSequence.addAll(sequence);
        });
        allSequence.forEach((item)->{System.out.println(item);});
        
    }

打印结果