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

Question

我需要以特定的顺序迭代地生成一个大集合的幂集。迭代地，我的意思是每次调用 getNext() （或类似的）我都会以特定顺序获得 powerset 的下一个元素。预先计算和存储整个 powerset 不是一个选项，因为它太大了；我说的是 200 项目集的 powerset。相反，当“无趣”的 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 元素实现了一个部分可行的解决方案，但到目前为止还无法弄清楚如何正确处理所有这些的逻辑。显然，0 个 1 和 5 个 1 以及 1 个 1 和 4 个 1 的集合是各自的镜像，有趣的情况是上面的中间情况，有两个 1 和三个 1。任何帮助，将不胜感激。

标签： javaiterationpowerset

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