生成功率集的所有元素

Question

/*
 * Power set is just set of all subsets for given set.
 * It includes all subsets (with empty set).
 * It's well-known that there are 2N elements in this set, where N is count of elements in original set.

 * To build power set, following thing can be used:

 * Create a loop, which iterates all integers from 0 till 2^N-1
 * Proceed to binary representation for each integer
 * Each binary representation is a set of N bits (for lesser numbers, add leading zeros).
 * Each bit corresponds, if the certain set member is included in current subset. 
 */
import java.util.NoSuchElementException;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
import java.util.List;
import java.util.ArrayList;


public class PowerSet<E> implements Iterator<Set<E>>, Iterable<Set<E>> {
    private final E[] ary;
    private final int subsets;
    private int i;

    public PowerSet(Set<E> set) {
        ary = (E[])set.toArray();
        subsets = (int)Math.pow(2, ary.length) - 1;
    }

    public Iterator<Set<E>> iterator() {
        return this;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Cannot remove()!");
    }

    @Override
    public boolean hasNext() {
        return i <= subsets;
    }

    @Override
    public Set<E> next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        Set<E> subset = new TreeSet<E>();
        BitSet bitSet = BitSet.valueOf(new long[] { i });
        // get the index of truth values.
        for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) {
            subset.add(ary[e]);
        }
        i++;
        return subset;
    }

    // Unit Test
    public static void main(String[] args) {
        Set<Integer> numbers = new TreeSet<Integer>();
        for (int i = 1; i < 5; i++) {
            numbers.add(i);
        }
        int count = 0;
        PowerSet<Integer> pSet = new PowerSet<Integer>(numbers);
        for (Set<Integer> subset : pSet) {
            //System.out.println(subset);
            count++;
        }
        assert count ==  (int)Math.pow(2, numbers.size()): "Total number of elements should be 2^N";
    }
}

代码运行良好。我也在努力学习用于单元测试的assert。主要的问题是，这些因素似乎不符合规则。有任何方法来维护lexicographical order吗？

Answer 1

2的

功率而不是使用： (int)Math.pow(2, numbers.size()) 您可以像这样更有效地计算2的幂： 1 << numbers.size() 如果你认为功率可能超过31，你可以用1L来计算它的长度。

手动位操作

与使用BitSet查找int中的1位不同，您可以使用整数算法自己检查比特：

    for (int bit = 0; bit < 32; bit++) {
        if ((i & (1 << bit)) != 0) {
            subset.add(ary[bit]);
        }
    }

Answer 2

关于维护顺序--我认为如果您将子集定义为SortedSet (这是TreeSet实现的另一个接口)，那么您将得到一个子集，其中元素按照它们的自然顺序排序(这是字典学的)，当然前提是它们是字符串。

在单元测试方面，Java中事实上的标准框架是Junit，它使用assert并对其进行增强。

Answer 3

*众所周知，这组中有2N元素

你的意思是2^N。

进口java.util.List；进口java.util.ArrayList；

这些进口产品未使用。

私人最终E[]系列；

拼出全名：array。或者更好的是，使用一个名称来描述这个字段的用途，比如allElements。

私有最终整数子集；

这应该是numSubsets。

一等兵i；

对于字段来说，i太短了。考虑使用currentSubsetIndex或其他描述性名称。

ary = (E[])set.toArray()；

这会触发未经检查的操作警告。您可能希望在构造函数之前使用@SuppressWarnings("unchecked")，或者使用这个版本 of Set#toArray。我不知道什么是首选的方法。

numSubsets = (int)Math.pow(2，array.length) - 1；

使用位移位，如@JS1建议的那样，以避免浮点舍入问题。

公共Iterator>迭代器(){返回此；}

在同一个iterator上调用PowerSet会返回相同的对象。因此，使用for-each循环在同一个PowerSet上循环两次将不能像预期的那样工作。迭代器不是迭代器。。

我还建议您使用@JS1's实现的next，并学习如何使用JUnit的@sharonbn建议。(也许测试套件也会成为很好的可审查代码。)

编辑：

主要的问题是，这些因素似乎不符合规则。有什么办法维持词典编纂的秩序吗？

集合是无序的。如果您希望为子集的元素指定一个特定的顺序，则不要使用Set (用于输入或输出)。