在Java中获取一个集的Powerset

Question

在Java中获取一个集的Powerset.的权力集{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)。)

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

这是我的欧拉项目图书馆.。*)