关于一个集合的子集的思考

之前做过很多类似的题目&＃xff0c;比如说给你一个字符串ABC&＃xff0c;然后请给出他的子集&＃xff08;A&＃xff0c;B&＃xff0c;C&＃xff0c;AB&＃xff0c;AC&＃xff0c;BC&＃xff0c;ABC&＃xff09;&＃xff0c;差不多都是这样的&＃xff0c;当然也有给你ABC&＃xff0c;请给出跟其长度一样的组合&＃xff08;ABC,ACB,BAC,BCA,CAB,CBA&＃xff09;等等。由于这种题目都是涉及到排列组合数学&＃xff0c;因此这里来总结一下。

1.首先我们来讨论第一种情况&＃xff0c;即给出一个集合&＃xff0c;求出其子集。

从数学角度&＃xff0c;我们可以知道&＃xff0c;拥有n个元素的集合&＃xff0c;它拥有2n个子集&＃xff08;包含空集的情况&＃xff09;&＃xff0c;因此我们的复杂度不可能会低于2n。

下面我们使用递归的方法来求。

• 终止条件&＃xff1a;n &＃61; 0&＃xff1b;

空集合只有一个子集{ }。

• 情况&＃xff1a;n &＃61; 1 ;

集合{a1}有2个子集&＃xff1a;{ }和{a1}.

• 情况&＃xff1a;n &＃61; 2;

集合{a1&＃xff0c;a2}有四个子集&＃xff1a;{ }&＃xff0c;{a1}&＃xff0c;{a2}&＃xff0c;{a1&＃xff0c;a2}。

从上面我们继续往下推断&＃xff0c;我们应该如何使用p&＃xff08;2&＃xff09;来构造p&＃xff08;3&＃xff09;&＃xff1f;

答案是复制p&＃xff08;2&＃xff09;&＃xff0c;并在这些子集中添加a3&＃xff0c;然后再将p&＃xff08;2&＃xff09;与其合并&＃xff0c;即可产生p&＃xff08;3&＃xff09;&＃xff1b;

下面是实现上述思路的代码&＃xff1a;

public ArrayList<ArrayList<Integer>> getR(ArrayList<Integer> set, int index){ArrayList<ArrayList<Integer>> allsubsets;if (set.size() &＃61;&＃61; index){// 终止条件allsubsets &＃61; new ArrayList<ArrayList<Integer>>();allsubsets.add(new ArrayList<Integer>());} else{allsubsets &＃61; getR(set, index &＃43; 1);int item &＃61; set.get(index);ArrayList<ArrayList<Integer>> biggersubsets &＃61; new ArrayList<ArrayList<Integer>>();// 存储p(3)for (ArrayList<Integer> subset : allsubsets)// subset是p(2)的一个子串&＃xff08;子串是用list表示的&＃xff09;{ArrayList<Integer> newlist &＃61; new ArrayList<>();// 不能覆盖p(2),因此需要重新起一个子串并在这些子串上操作newlist.addAll(subset);newlist.add(item);// 每个子串都添加a3biggersubsets.add(newlist);// 子串加入p(3)}allsubsets.addAll(biggersubsets);// p(3)加入总结果}return allsubsets;}

另外一种思路是&＃xff0c;每个元素在子集中的出现都是2种情况&＃xff0c;有或者没有这种元素&＃xff0c;因此我们构造0-2n−1个连续的二进制数&＃xff0c;用他们每一位的表示来标识元素出现的情况。

下面是代码&＃xff1a;

public ArrayList> getSub(ArrayList set){ArrayList> allsubsets &＃61; new ArrayList>();int max &＃61; 1 <<set.size();for (int k &＃61; 0; k subset &＃61; convertIntToset(k, set);// 将k代表的二进制数化为子集。allsubsets.add(subset);}return allsubsets;}public ArrayList convertIntToset(int x, ArrayList set){ArrayList subset &＃61; new ArrayList<>();int index &＃61; 0;for (int k &＃61; x; k > 0; k >>&＃61; 1){if ((k & 1) &＃61;&＃61; 1)// 取最后一位{subset.add(set.get(index));}index&＃43;&＃43;;}return subset;}

第二种情况是不求子集&＃xff0c;而是求组合的情况。

详细见我的这篇博客