Java - 按特定顺序迭代生成powerset

Question

我需要按特定顺序迭代生成大集的powerset。迭代地，我的意思是每次调用getNext（）（或类似的）时，我都会按特定顺序获取powerset的下一个元素。预先计算和存储整个powerset不是一种选择，因为它太大了;我说的是200件套装的发电机组。相反，当“不感兴趣”的powerset元素出现时，特定的顺序将允许我优化并跳过。

对于有序的五个项目集，指定的顺序如下所示，其中1表示要包括powerset元素中的项目（从左到右，从上到下）：

00000 10000 11000 11100 11110 11111
      01000 10100 11010 11101
      00100 10010 11001 11011
      00010 10001 10110 10111
      00001 01100 10101 01111
            01010 10011
            01001 01110
            00110 01101
            00101 01011
            00011 00111

“跳过前进”是指如果我确定10010不满足某些标准，我知道以下没有一个具有两个1的powerset元素将满足该标准，所以我可以跳过来检查powerset元素有三个1。

我已经使用移位powerset元素的部分实现了部分工作的解决方案，但到目前为止还没有找到如何正确处理所有这些的逻辑。显然，零1和5 1的集合，以及1 1和4 1是各自的镜像，有趣的情况是上面的中间，有两个1和3个1。任何帮助，将不胜感激。

Answer 1

以正确的方式思考这一点，它变得相当微不足道。

/***************** PowerSetIterator.java **********************************/
/**
 * @author OppfinnarJocke
 */
/* This class iteratively generates the power set (except for the empty set)
 * First it generates all subsets of num_slots 1, then of num_slots 2, ... 
  * then of num_slots len (of which there is only one)
 */
public class PowerSetIterator
{
    private final int len;
    private final int[] slots;
    private int num_slots;

    public PowerSetIterator(final int len)
    {
        this.len = len;
        this.slots = new int[this.len];
        this.num_slots = 0;
    }

    public int[] next()
    {
        recurse(this.num_slots);

        return this.slots;
    }

    private int recurse(final int right_slot)
    {       
        final int this_slot = right_slot - 1;
        //if(this_slot < 0)
        //  return this.len - this.num_slots;
        assert this_slot >= 0 : "index cannot be < 0";
        // Cannot really grok why this never happens...

        if(!this.isExhausted(this_slot))
            this.slots[this_slot]++;
        else
            this.slots[this_slot] = recurse(this_slot);

        return this.slots[this_slot] + 1;
    }

    /**
     * Skips to next num_slots, and sets up for subsequent iterations
     *
     * @return false if num_slots >= len, that is, if we have already exhausted the powerset generation
     */
    public final boolean nextSize()
    {
        if(this.num_slots >= this.len)
            return false;

        this.num_slots++;
        for(int i = 0; i < this.num_slots; i++)
            this.slots[i] = i;

        return true;
    }

    /**
     * Checks if the last num_slots elements have all reached their end indexes.
     *
     * @return true if the powerset for this num_slots has been enumerated
     */
    public boolean doneWithThisSize()
    {
        for(int i = 0; i < this.num_slots; i++)
            if(isExhausted(i) == false)
                return false;

        return true;
    }

    /**
     * We are finished when len number of slots have been occupied. 
     * 
     * @return true if all sizes and combinations have been exhausted
     */
    public boolean isFinished()
    {
        return this.num_slots == this.len;
    }

    /**
     * Determine whether this slot has exhausted its indexes. Slots hold values between 
     * slot_index <= slots[slot_index] <= num_items - num_slots + slot_index
     * 
     * @param slot_index Index of the slot to check
     * @return true if the slot at slot_index is at or beyond its range
     */
    private boolean isExhausted(final int slot_index)
    {
        assert slot_index <= this.slots[slot_index] : "Slot value below slot_index";

        return this.slots[slot_index] >= this.len - this.num_slots + slot_index;
    }

    @Override
    public String toString()
    {
        StringBuilder buf = new StringBuilder();
        for(int i = 0; i < this.num_slots; i++)
        {
            buf.append(this.slots[i]);
            buf.append(',');
        }

        buf.setLength(buf.length()-1);

        return buf.toString();
    }

    public String toBitString()
    {
        final char[] charray = new char[this.len];
        java.util.Arrays.fill(charray, '0');

        // Fill the correct postions with 1's
        for(int i = 0; i < this.num_slots; i++)
        {
            final int index = this.slots[i];
            charray[index] = '1';
        }

        final String bit_string = new String(charray);
        return bit_string;
    }


    public static void main(String[] args)
    {
        final int LENGTH = 5;
        PowerSetIterator set_it = new PowerSetIterator(LENGTH);

        while(!set_it.isFinished())
        {
            set_it.nextSize();
            print_it(set_it);

            while(!set_it.doneWithThisSize())
            {
                set_it.next();
                print_it(set_it);
            }
        }
    }

    private static void print_it(final PowerSetIterator set_it)
    {
        System.out.println("set_it.toString() = " + set_it.toString());
        System.out.println("set_it.toBitString() = " + set_it.toBitString());       
    }
}