Java中获取集合的幂集

Question

{1, 2, 3} 的幂集为：

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3 }, {1, 2, 3}, {1}}

假设我有一个 Java Set：

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)。）

Answer 1

是的，确实是 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);
 }

Answer 2

实际上，我已经编写了在 O(1) 中完成您所要求的代码。问题是您接下来打算用该集合做什么。如果您只是要对其调用 size() ，那么时间复杂度为 O(1)，但如果您要迭代它，则显然是 O(2^n)。

contains() 将是 O(n) 等。

您真的需要这个吗？

编辑：

此代码是现已在 Guava 中提供，通过 Sets.powerSet(set)。

Answer 3

这是我使用生成器的解决方案，优点是，整个幂集永远不会立即存储......因此您可以逐一迭代它，而不需要将其存储在内存中。我想认为这是一个更好的选择...请注意，复杂性是相同的，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 Library...:)

Answer 4

如果 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;

Answer 5

这里是一个教程，详细描述了你想要的，包括代码。你是对的，复杂度是 O(2^n)。

Answer 6

我根据@Harry He 的想法提出了另一个解决方案。可能不是最优雅的，但按照我的理解，它是这样的：

让我们以经典的简单示例 SP(S) = {{1},{2},{3}} 的 PowerSet 为例。
我们知道获取子集数量的公式是2^n（7 + 空集）。
对于此示例，2^3 = 8 个子集。

为了找到每个子集，我们需要将 0-7 十进制转换为二进制表示形式，如下转换表所示：

If我们逐行遍历表，每一行都会产生一个子集，每个子​​集的值将来自启用的位。

Bin Value 部分中的每一列对应于原始输入集中的索引位置。

这是我的代码：

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;
}

}

Answer 7

如果您使用 Eclipse Collections （以前的 GS Collections)，您可以在所有 SetIterables 上使用 powerSet() 方法。

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 的提交者。

Answer 8

我正在寻找一个不像这里发布的解决方案那么大的解决方案。这是针对 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()));
}

Answer 9

这是一个简单的迭代 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;
}

Answer 10

当集合的大小很大时，上面的一些解决方案会受到影响，因为它们会创建大量要收集的对象垃圾并需要复制数据。我们怎样才能避免这种情况呢？我们可以利用这样一个事实：我们知道结果集大小有多大（2^n），预先分配一个那么大的数组，然后追加到它的末尾，而不是复制。

加速比随 n 快速增长。我将其与上面 João Silva 的解决方案进行了比较。在我的机器上（所有测量值均为近似值），n=13 快 5 倍，n=14 快 7 倍，n=15 快 12 倍，n=16 快 25 倍，n=17 快 75 倍，n=18 快 140 倍。因此，垃圾创建/收集和复制在看似类似的大 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;
}

Answer 11

以下解决方案借用自我的书《编码面试：问题、分析和解决方案"：

选择数组中的一些整数组成组合。使用一组位，其中每个位代表数组中的一个整数。如果组合中选择了第i个字符，则第i位为1；例如，数组[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。例如，为了用位 {1, 0, 1} 增加数字 5，它从右侧清除 1 位并将最右边的 0 位设置为 1。这些位变为{1, 1, 0} 表示数字 6，它是 5 加 1 的结果。

Answer 12

import java.util.Set;
import com.google.common.collect.*;

Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));

Answer 13

如果 S 是包含 N 个元素的有限集，则 S 的幂集包含 2^N 个元素。简单枚举幂集元素的时间为 2^N，因此 O(2^N) 是（急切地）构造幂集的时间复杂度的下限。

简而言之，任何涉及创建幂集的计算都不会针对较大的 N 值进行扩展。没有聪明的算法可以帮助您......除了避免创建幂集的需要之外！

Answer 14

一种不使用递归的方法如下：使用二进制掩码并进行所有可能的组合。

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;

    }

}

Answer 15

算法：

输入：Set[], set_size
1. 获取幂集大小
poweret_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;
}

Answer 16

这是我的递归解决方案，它可以使用 Java 泛型获取任何集合的幂集。它的主要思想是将输入数组的头部与数组其余部分的所有可能的解决方案组合起来，如下所示。

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);
    }
}

这将输出：

[[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], []]

Answer 17

另一个示例实现：

 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();
        }
    }

Answer 18

这是我使用 lambda 的方法。

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%

Answer 19

// 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;
    }

}

Answer 20

我最近不得不使用类似的东西，但首先需要最小的子列表（有 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
}

通过这种方式，也很容易将其限制为特定长度的子列表。

Answer 21

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();
        } 
    }
}

Answer 22

另一种解决方案 - 使用 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);

}

/* Prints : [][a][b][c][d][e][a, b][a, c][b, c] */

Answer 23

我们可以使用或不使用递归来编写幂集。这是一个没有递归的尝试：

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;
}

Answer 24

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;
    }

Answer 25

这里是生成一个幂集。这个想法是first = S[0]，较小的集合是S[1,...n]。

计算smallerSet的所有子集并将它们放入allsubsets中。

对于 allsubsets 中的每个子集，克隆它并首先添加到子集中。

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;
}

Answer 26

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>();
}

Answer 27

该函数通过递归解决了这个问题，但将名为 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);
}

Answer 28

只需使用递归即可。

public class Combinations {

// A recursive method that prints all combinations of any size of the first n elements of an array
    public static void printCombinations(String[] arr, int n, String current) {
    // Base case: if n is 0, print the current combination
        if (n == 0) {
            System.out.println(current);
            return;
        }
    // Recursive case: for each element, either include it or exclude it from the current combination and recursively call printCombinations with n-1
        printCombinations(arr, n-1, current + arr[n-1] + " "); // include
        printCombinations(arr, n-1, current); // exclude
    }

    public static void main(String[] args) {
        // Read in the command line argument
       int n = Integer.parseInt(args[0]);
        // Well my array in this case consists of first 6 letters of the alphabet
        String[] arr = new String[n];
        arr[0] = "a";
        arr[1] = "b";
        arr[2] = "c";
        arr[3] = "d";
        arr[4] = "e";
        arr[5] = "f";
        // Call the recursive method with an empty current combination
        printCombinations(arr, n, "");
    }
}