的幂集{1, 2, 3}是：
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
假设我Set在 Java 中有一个：
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
如何以尽可能好的复杂性顺序编写函数 getPowerset？（我认为它可能是 O(2^n)。）
是的，O(2^n)确实如此，因为您需要生成2^n可能的组合。这是一个使用泛型和集合的工作实现：
public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<Set<T>>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<T>());
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
并根据您的示例输入进行测试：
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
System.out.println(s);
}
实际上，我编写的代码可以满足您在 O(1) 中的要求。问题是你接下来打算用 Set做什么。如果你只是要调用size()它，那就是 O(1)，但如果你要迭代它，那显然是O(2^n).
contains()会是O(n)，等等。
你真的需要这个吗？
编辑：
该代码现在在 Guava 中可用，通过方法公开Sets.powerSet(set)。
这是我使用生成器的解决方案，其优点是，整个电源组永远不会一次存储......因此您可以一个接一个地对其进行迭代，而无需将其存储在内存中。我想这是一个更好的选择......注意复杂性是相同的，O（2 ^ n），但内存需求减少了（假设垃圾收集器的行为！;））
/**
*
*/
package org.mechaevil.util.Algorithms;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* @author st0le
*
*/
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
private E[] arr = null;
private BitSet bset = null;
@SuppressWarnings("unchecked")
public PowerSet(Set<E> set)
{
arr = (E[])set.toArray();
bset = new BitSet(arr.length + 1);
}
@Override
public boolean hasNext() {
return !bset.get(arr.length);
}
@Override
public Set<E> next() {
Set<E> returnSet = new TreeSet<E>();
for(int i = 0; i < arr.length; i++)
{
if(bset.get(i))
returnSet.add(arr[i]);
}
//increment bset
for(int i = 0; i < bset.size(); i++)
{
if(!bset.get(i))
{
bset.set(i);
break;
}else
bset.clear(i);
}
return returnSet;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not Supported!");
}
@Override
public Iterator<Set<E>> iterator() {
return this;
}
}
要调用它，请使用以下模式：
Set<Character> set = new TreeSet<Character> ();
for(int i = 0; i < 5; i++)
set.add((char) (i + 'A'));
PowerSet<Character> pset = new PowerSet<Character>(set);
for(Set<Character> s:pset)
{
System.out.println(s);
}
它来自我的 Project Euler 库... :)
如果 n < 63，这是一个合理的假设，因为无论如何尝试构造幂集都会耗尽内存（除非使用迭代器实现），这是一种更简洁的方法。二进制操作比Math.pow()掩码的数组快得多，但不知何故 Java 用户害怕它们......
List<T> list = new ArrayList<T>(originalSet);
int n = list.size();
Set<Set<T>> powerSet = new HashSet<Set<T>>();
for( long i = 0; i < (1 << n); i++) {
Set<T> element = new HashSet<T>();
for( int j = 0; j < n; j++ )
if( (i >> j) % 2 == 1 ) element.add(list.get(j));
powerSet.add(element);
}
return powerSet;
这是一个准确描述您想要的内容的教程，包括代码。你是对的，复杂度是 O(2^n)。
我根据@Harry He 的想法提出了另一个解决方案。可能不是最优雅的，但据我了解：
让我们以 SP(S) = {{1},{2},{3}} 的经典简单示例 PowerSet 为例。我们知道得到子集数量的公式是 2^n（7 + 空集）。对于此示例，2^3 = 8 个子集。
为了找到每个子集，我们需要将 0-7 十进制转换为二进制表示，如下面的转换表所示：
如果我们逐行遍历表，每一行都会产生一个子集，每个子集的值将来自启用的位。
Bin Value 部分中的每一列对应于原始输入 Set 中的索引位置。
这是我的代码：
public class PowerSet {
/**
* @param args
*/
public static void main(String[] args) {
PowerSet ps = new PowerSet();
Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);
for (Set<Integer> s : ps.powerSet(set)) {
System.out.println(s);
}
}
public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
// Original set size e.g. 3
int size = originalSet.size();
// Number of subsets 2^n, e.g 2^3 = 8
int numberOfSubSets = (int) Math.pow(2, size);
Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
for (int i = 0; i < numberOfSubSets; i++) {
// Get binary representation of this index e.g. 010 = 2 for n = 3
String bin = getPaddedBinString(i, size);
//Get sub-set
Set<Integer> set = getSet(bin, originalList));
sets.add(set);
}
return sets;
}
//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
Set<Integer> result = new HashSet<Integer>();
for(int i = bin.length()-1; i >= 0; i--){
//Only get sub-sets where bool flag is on
if(bin.charAt(i) == '1'){
int val = origValues.get(i);
result.add(val);
}
}
return result;
}
//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
String bin = Integer.toBinaryString(i);
bin = String.format("%0" + size + "d", Integer.parseInt(bin));
return bin;
}
}
如果您使用的是Eclipse Collections（以前称为GS Collections），则可以powerSet()在所有 SetIterables 上使用该方法。
MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
注意：我是 Eclipse Collections 的提交者。
这是一个简单的迭代 O(2^n) 解决方案：
public static Set<Set<Integer>> powerSet(List<Integer> intList){
Set<Set<Integer>> result = new HashSet();
result.add(new HashSet());
for (Integer i : intList){
Set<Set<Integer>> temp = new HashSet();
for(Set<Integer> intSet : result){
intSet = new HashSet(intSet);
intSet.add(i);
temp.add(intSet);
}
result.addAll(temp);
}
return result;
}
我一直在寻找一个不像这里发布的那么大的解决方案。这针对 Java 7，因此对于版本 5 和 6 将需要少量粘贴。
Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
Set<Set<Object>> powerSet = new HashSet<>(),
runSet = new HashSet<>(),
thisSet = new HashSet<>();
while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
if (powerSet.isEmpty()) {
for (Object o : orig) {
Set<Object> s = new TreeSet<>();
s.add(o);
runSet.add(s);
powerSet.add(s);
}
continue;
}
for (Object o : orig) {
for (Set<Object> s : runSet) {
Set<Object> s2 = new TreeSet<>();
s2.addAll(s);
s2.add(o);
powerSet.add(s2);
thisSet.add(s2);
}
}
runSet.clear();
runSet.addAll(thisSet);
thisSet.clear();
}
powerSet.add(new TreeSet());
return powerSet;
这是一些要测试的示例代码：
Set<Object> hs = new HashSet<>();
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(4);
for(Set<Object> s : powerSetofNodes(hs)) {
System.out.println(Arrays.toString(s.toArray()));
}
当集合的大小很大时，上述一些解决方案会受到影响，因为它们会创建大量要收集的对象垃圾并需要复制数据。我们怎样才能避免呢？我们可以利用我们知道结果集大小（2^n）的事实，预先分配一个那么大的数组，然后附加到它的末尾，从不复制。
加速比随着 n 快速增长。我将它与上述 João Silva 的解决方案进行了比较。在我的机器上（所有测量值都是近似值），n=13 快 5 倍，n=14 是 7x，n=15 是 12x，n=16 是 25x，n=17 是 75x，n=18 是 140x。因此，垃圾创建/收集和复制在其他看似类似的大 O 解决方案中占据主导地位。
与让它动态增长相比，在开始时预分配数组似乎是一种胜利。当 n=18 时，动态增长需要大约两倍的时间。
public static <T> List<List<T>> powerSet(List<T> originalSet) {
// result size will be 2^n, where n=size(originalset)
// good to initialize the array size to avoid dynamic growing
int resultSize = (int) Math.pow(2, originalSet.size());
// resultPowerSet is what we will return
List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize);
// Initialize result with the empty set, which powersets contain by definition
resultPowerSet.add(new ArrayList<T>(0));
// for every item in the original list
for (T itemFromOriginalSet : originalSet) {
// iterate through the existing powerset result
// loop through subset and append to the resultPowerset as we go
// must remember size at the beginning, before we append new elements
int startingResultSize = resultPowerSet.size();
for (int i=0; i<startingResultSize; i++) {
// start with an existing element of the powerset
List<T> oldSubset = resultPowerSet.get(i);
// create a new element by adding a new item from the original list
List<T> newSubset = new ArrayList<T>(oldSubset);
newSubset.add(itemFromOriginalSet);
// add this element to the result powerset (past startingResultSize)
resultPowerSet.add(newSubset);
}
}
return resultPowerSet;
}
以下解决方案是从我的《编码面试：问题、分析和解决方案》一书中借用的：
选择数组中的一些整数组成一个组合。使用了一组位，其中每个位代表数组中的一个整数。如果选择第i 个字符进行组合，则第i位为 1；否则为0。例如，数组[1,2,3]的组合使用三位。如果选择前两个整数1和2组成一个组合[1, 2]，则对应的位为{1, 1, 0}。类似地，对应于另一个组合[1, 3]的位是{1, 0, 1}。如果我们能得到所有可能的n位组合，我们就能得到一个长度为n的数组的所有组合。
一个数字由一组位组成。n位的所有可能组合对应于从 1 到 2^ n -1 的数字。因此，1 到 2^ n -1 范围内的每个数字对应于长度为n的数组的组合。例如数字 6 由位 {1,1,0} 组成，因此在数组 [1,2,3] 中选择第一个和第二个字符来生成组合 [1,2]。类似地，具有位 {1, 0, 1} 的数字 5 对应于组合 [1, 3]。
实现此解决方案的 Java 代码如下所示：
public static ArrayList<ArrayList<Integer>> powerSet(int[] numbers) {
ArrayList<ArrayList<Integer>> combinations = new ArrayList<ArrayList<Integer>>();
BitSet bits = new BitSet(numbers.length);
do{
combinations.add(getCombination(numbers, bits));
}while(increment(bits, numbers.length));
return combinations;
}
private static boolean increment(BitSet bits, int length) {
int index = length - 1;
while(index >= 0 && bits.get(index)) {
bits.clear(index);
--index;
}
if(index < 0)
return false;
bits.set(index);
return true;
}
private static ArrayList<Integer> getCombination(int[] numbers, BitSet bits){
ArrayList<Integer> combination = new ArrayList<Integer>();
for(int i = 0; i < numbers.length; ++i) {
if(bits.get(i))
combination.add(numbers[i]);
}
return combination;
}
方法增量增加一组位中表示的数字。该算法从最右边的位清除 1 位，直到找到 0 位。然后它将最右边的 0 位设置为 1。例如，为了增加数字 5 的位 {1,0,1}，它从右侧清除 1 位并将最右边的 0 位设置为 1。这些位变为{1, 1, 0} 表示数字 6，它是 5 加 1 的结果。
import java.util.Set;
import com.google.common.collect.*;
Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));
没有递归的一种方法如下：使用二进制掩码并进行所有可能的组合。
public HashSet<HashSet> createPowerSet(Object[] array)
{
HashSet<HashSet> powerSet=new HashSet();
boolean[] mask= new boolean[array.length];
for(int i=0;i<Math.pow(2, array.length);i++)
{
HashSet set=new HashSet();
for(int j=0;j<mask.length;j++)
{
if(mask[i])
set.add(array[j]);
}
powerSet.add(set);
increaseMask(mask);
}
return powerSet;
}
public void increaseMask(boolean[] mask)
{
boolean carry=false;
if(mask[0])
{
mask[0]=false;
carry=true;
}
else
mask[0]=true;
for(int i=1;i<mask.length;i++)
{
if(mask[i]==true && carry==true)
mask[i]=false;
else if (mask[i]==false && carry==true)
{
mask[i]=true;
carry=false;
}
else
break;
}
}
如果 S 是具有 N 个元素的有限集，则 S 的幂集包含 2^N 个元素。简单枚举幂集元素的时间是 2^N，因此O(2^N)（急切地）构建幂集的时间复杂度的下限也是如此。
简而言之，任何涉及创建幂集的计算都不会针对较大的 N 值进行扩展。没有聪明的算法可以帮助您……除了避免创建幂集的需要！
This is my recursive solution which can get the power set of any set using Java Generics. Its main idea is to combine the head of the input array with all the possible solutions of the rest of the array as follows.
import java.util.LinkedHashSet;
import java.util.Set;
public class SetUtil {
private static<T> Set<Set<T>> combine(T head, Set<Set<T>> set) {
Set<Set<T>> all = new LinkedHashSet<>();
for (Set<T> currentSet : set) {
Set<T> outputSet = new LinkedHashSet<>();
outputSet.add(head);
outputSet.addAll(currentSet);
all.add(outputSet);
}
all.addAll(set);
return all;
}
//Assuming that T[] is an array with no repeated elements ...
public static<T> Set<Set<T>> powerSet(T[] input) {
if (input.length == 0) {
Set <Set<T>>emptySet = new LinkedHashSet<>();
emptySet.add(new LinkedHashSet<T>());
return emptySet;
}
T head = input[0];
T[] newInputSet = (T[]) new Object[input.length - 1];
for (int i = 1; i < input.length; ++i) {
newInputSet[i - 1] = input[i];
}
Set<Set<T>> all = combine(head, powerSet(newInputSet));
return all;
}
public static void main(String[] args) {
Set<Set<Integer>> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6});
System.out.println(set);
}
}
This will output:
[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []]
算法：
输入：Set[], set_size 1. 获取幂集的大小 powet_set_size = pow(2, set_size) 2 循环计数器从 0 到 pow_set_size (a) 循环 i = 0 到 set_size (i) 如果计数器中的第 i 位是为该子集打印集合中的第 i 个元素 (b) 为子集打印分隔符，即换行符
#include <stdio.h>
#include <math.h>
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1<<j))
printf("%c", set[j]);
}
printf("\n");
}
}
/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c'};
printPowerSet(set, 3);
getchar();
return 0;
}这是我使用 lambdas 的方法。
public static <T> Set<Set<T>> powerSet(T[] set) {
return IntStream
.range(0, (int) Math.pow(2, set.length))
.parallel() //performance improvement
.mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet()))
.map(Function.identity())
.collect(Collectors.toSet());
}
或并行（参见 parallel() 注释）：
输入集大小：18
逻辑处理器：8 à 3.4GHz
性能提升：30%
另一个示例实现：
public static void main(String args[])
{
int[] arr = new int[]{1,2,3,4};
// Assuming that number of sets are in integer range
int totalSets = (int)Math.pow(2,arr.length);
for(int i=0;i<totalSets;i++)
{
String binaryRep = Integer.toBinaryString(i);
for(int j=0;j<binaryRep.length();j++)
{
int index=binaryRep.length()-1-j;
if(binaryRep.charAt(index)=='1')
System.out.print(arr[j] +" ");
}
System.out.println();
}
}
t 的子集是可以通过删除 t 的零个或多个元素而得到的任何集合。withoutFirst 子集添加 t 中缺少第一个元素的子集，for 循环将处理添加带有第一个元素的子集。例如，如果 t 包含元素 ["1", "2", "3"]，missingFirst 将添加 [[""], ["2"], ["3"], ["2","3 "]] 并且 for 循环会将 "1" 粘贴在这些元素的前面并将其添加到 newSet 中。所以我们最终会得到 [[""], ["1"], ["2"], ["3"], ["1", "2"], ["1", "3"] , ["2","3"], ["1", "2", "3"]]。
public static Set<Set<String>> allSubsets(Set<String> t) {
Set<Set<String>> powerSet = new TreeSet<>();
if(t.isEmpty()) {
powerSet.add(new TreeSet<>());
return powerSet;
}
String first = t.get(0);
Set<Set<String>> withoutFirst = allSubsets(t.subSet(1, t.size()));
for (List<String> 1st : withoutFirst) {
Set<String> newSet = new TreeSet<>();
newSet.add(first);
newSet.addAll(lst);
powerSet.add(newSet);
}
powerSet.addAll(withoutFirst);
return powerSet;
}
// input: S
// output: P
// S = [1,2]
// P = [], [1], [2], [1,2]
public static void main(String[] args) {
String input = args[0];
String[] S = input.split(",");
String[] P = getPowerSet(S);
if (P.length == Math.pow(2, S.length)) {
for (String s : P) {
System.out.print("[" + s + "],");
}
} else {
System.out.println("Results are incorrect");
}
}
private static String[] getPowerSet(String[] s) {
if (s.length == 1) {
return new String[] { "", s[0] };
} else {
String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length));
String[] subP2 = new String[subP1.length];
for (int i = 0; i < subP1.length; i++) {
subP2[i] = s[0] + subP1[i];
}
String[] P = new String[subP1.length + subP2.length];
System.arraycopy(subP1, 0, P, 0, subP1.length);
System.arraycopy(subP2, 0, P, subP1.length, subP2.length);
return P;
}
}
public class PowerSet {
public static List<HashSet<Integer>> powerset(int[] a) {
LinkedList<HashSet<Integer>> sets = new LinkedList<HashSet<Integer>>();
int n = a.length;
for (int i = 0; i < 1 << n; i++) {
HashSet<Integer> set = new HashSet<Integer>();
for (int j = 0; j < n; j++) {
if ((1 << j & i) > 0)
set.add(a[j]);
}
sets.add(set);
}
return sets;
}
public static void main(String[] args) {
List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 });
for (HashSet<Integer> set : sets) {
for (int i : set)
System.out.print(i);
System.out.println();
}
}
}
该函数通过递归解决了这个问题，但将名为 powerset 的变量设为全局变量：
static ArrayList<ArrayList<Integer>> powerSet = new ArrayList<>();
public static void getPowerSet(Queue<Integer> a) {
int n = a.poll();
if (!a.isEmpty()) {
getPowerSet(a);
}
int s = powerSet.size();
for (int i = 0; i < s; i++) {
ArrayList<Integer> ne = new ArrayList<>();
for (int j = 0; j < powerSet.get(i).size(); j++) {
ne.add(powerSet.get(i).get(j));
}
ne.add(n);
powerSet.add(ne);
}
ArrayList<Integer> p = new ArrayList<>();
p.add(n);
powerSet.add(p);
}
我最近不得不使用这样的东西，但首先需要最小的子列表（有 1 个元素，然后是 2 个元素，...）。我不想包括空的或整个列表。另外，我不需要返回所有子列表的列表，我只需要对每个子列表做一些事情。
想要在没有递归的情况下做到这一点，并提出了以下内容（将“正在做的事情”抽象为功能接口）：
@FunctionalInterface interface ListHandler<T> {
void handle(List<T> list);
}
public static <T> void forAllSubLists(final List<T> list, ListHandler handler) {
int ll = list.size(); // Length of original list
int ci[] = new int[ll]; // Array for list indices
List<T> sub = new ArrayList<>(ll); // The sublist
List<T> uml = Collections.unmodifiableList(sub); // For passing to handler
for (int gl = 1, gm; gl <= ll; gl++) { // Subgroup length 1 .. n-1
gm = 0; ci[0] = -1; sub.add(null); // Some inits, and ensure sublist is at least gl items long
do {
ci[gm]++; // Get the next item for this member
if (ci[gm] > ll - gl + gm) { // Exhausted all possibilities for this position
gm--; continue; // Continue with the next value for the previous member
}
sub.set(gm, list.get(ci[gm])); // Set the corresponding member in the sublist
if (gm == gl - 1) { // Ok, a sublist with length gl
handler.handle(uml); // Handle it
} else {
ci[gm + 1] = ci[gm]; // Starting value for next member is this
gm++; // Continue with the next member
}
} while (gm >= 0); // Finished cycling through all possibilities
} // Next subgroup length
}
通过这种方式，也很容易将其限制为特定长度的子列表。
另一个解决方案 - 使用 java8+ 流 api 它是惰性且有序的，因此当它与“limit()”一起使用时它会返回正确的子集。
public long bitRangeMin(int size, int bitCount){
BitSet bs = new BitSet(size);
bs.set(0, bitCount);
return bs.toLongArray()[0];
}
public long bitRangeMax(int size, int bitCount){
BitSet bs = BitSet.valueOf(new long[]{0});
bs.set(size - bitCount, size);
return bs.toLongArray()[0];
}
public <T> Stream<List<T>> powerSet(Collection<T> data)
{
List<T> list = new LinkedHashSet<>(data).stream().collect(Collectors.toList());
Stream<BitSet> head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i}));
Stream<BitSet> tail = IntStream.rangeClosed(1, list.size())
.boxed()
.flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1))
.mapToObj(v2 -> BitSet.valueOf(new long[]{v2}))
.filter( bs -> bs.cardinality() == v1));
return Stream.concat(head, tail)
.map( bs -> bs
.stream()
.mapToObj(list::get)
.collect(Collectors.toList()));
}
客户端代码是
@Test
public void testPowerSetOfGivenCollection(){
List<Character> data = new LinkedList<>();
for(char i = 'a'; i < 'a'+5; i++ ){
data.add(i);
}
powerSet(data)
.limit(9)
.forEach(System.out::print);
}
/* 打印：[][a][b][c][d][e][a, b][a, c][b, c] */
我们可以使用或不使用递归来编写幂集。这是没有递归的尝试：
public List<List<Integer>> getPowerSet(List<Integer> set) {
List<List<Integer>> powerSet = new ArrayList<List<Integer>>();
int max = 1 << set.size();
for(int i=0; i < max; i++) {
List<Integer> subSet = getSubSet(i, set);
powerSet.add(subSet);
}
return powerSet;
}
private List<Integer> getSubSet(int p, List<Integer> set) {
List<Integer> subSet = new ArrayList<Integer>();
int position = 0;
for(int i=p; i > 0; i >>= 1) {
if((i & 1) == 1) {
subSet.add(set.get(position));
}
position++;
}
return subSet;
}
package problems;
import java.util.ArrayList;
import java.util.List;
public class SubsetFinderRecursive {
public static void main(String[] args) {
//input
int[] input = new int[3];
for(int i=0; i<input.length; i++) {
input[i] = i+1;
}
// root node of the tree
Node root = new Node();
// insert values into tree
for(int i=0; i<input.length; i++) {
insertIntoTree(root, input[i]);
}
// print leaf nodes for subsets
printLeafNodes(root);
}
static void printLeafNodes(Node root) {
if(root == null) {
return;
}
// Its a leaf node
if(root.left == null && root.right == null) {
System.out.println(root.values);
return;
}
// if we are not at a leaf node, then explore left and right
if(root.left !=null) {
printLeafNodes(root.left);
}
if(root.right != null) {
printLeafNodes(root.right);
}
}
static void insertIntoTree(Node root, int value) {
// Error handling
if(root == null) {
return;
}
// if there is a sub tree then go down
if(root.left !=null && root.right != null) {
insertIntoTree(root.left, value);
insertIntoTree(root.right, value);
}
// if we are at the leaf node, then we have 2 choices
// Either exclude or include
if(root.left == null && root.right == null) {
// exclude
root.left = new Node();
root.left.values.addAll(root.values);
// include
root.right = new Node();
root.right.values.addAll(root.values);
root.right.values.add(value);
return;
}
}
}
class Node {
Node left;
Node right;
List<Integer> values = new ArrayList<Integer>();
}
这里是生成一个幂集。这个想法是 first =S[0]和较小的集合是S[1,...n]。
计算 smallSet 的所有子集并将它们放入所有子集中。
对于所有子集中的每个子集，克隆它并首先添加到子集中。
ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set, int index){
ArrayList<ArrayList<Integer>> allsubsets;
if(set.size() == index){
allsubsets = new ArrayList<ArrayList<Integer>>();
allsubsets.add(new ArrayList<Integer>()); // the empty set
}else{
allsubsets = getSubsets(set, index+1);
int item = set.get(index);
ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> subset: allsubsets){
ArrayList<Integer> newsubset = new ArrayList<Integer>();
newsubset.addAll(subset);
newsubset.add(item);
moresubsets.add(newsubset);
}
moresubsets.addAll(moresubsets);
}
return allsubsets;
}