Java中按数学顺序生成幂集的迭代算法

public static boolean advance(boolean[] flags)

import java.util.Arrays;

class Subsets {

    /**
     * 推进布尔标志数组到下一个按数学顺序排列的子集状态。
     *
     * @param flags 布尔标志数组，每个元素代表原始集合中对应元素的包含状态。
     * @return 如果成功推进到下一个子集，则返回 true；如果已生成所有子集（当前是全集），则返回 false。
     */
    public static boolean advance(boolean[] flags) {
        int count = 0; // 记录当前位置之前true标志的数量
        for (int i = 0; i < flags.length; ++i) {
            if (flags[i]) {
                ++count; // 遇到true，增加计数
            } else {
                // 找到一个false标志，且之前有至少一个true标志
                if (count > 0) {
                    flags[i] = true; // 将当前false设为true
                    // 将前 (count-1) 个标志设为true，以保持词典顺序
                    for (int j = 0; j < (count - 1); ++j) {
                        flags[j] = true;
                    }
                    // 将 (count-1) 到 i-1 之间的标志设为false
                    for (int j = (count - 1); j < i; ++j) {
                        flags[j] = false;
                    }
                    return true; // 成功推进
                }
            }
        }

        // 遍历到数组末尾，没有找到合适的false标志
        if (count == flags.length) {
            return false; // 所有标志都为true，已生成全集，算法结束
        }

        // 当前true标志已全部移到末尾，需要增加子集基数
        // 将前 (count+1) 个标志设为true，其余设为false
        for (int i = 0; i <= count; ++i) {
            flags[i] = true;
        }
        for (int i = count + 1; i < flags.length; ++i) {
            flags[i] = false;
        }
        return true; // 成功推进到下一个基数的第一个子集
    }

    /**
     * 打印布尔标志数组的状态。
     *
     * @param flags 布尔标志数组。
     */
    public static void dump(boolean[] flags) {
        for (int i = 0; i < flags.length; ++i) {
            System.out.print(flags[i] ? 'Y' : 'N');
        }
        System.out.println();
    }

    /**
     * 根据布尔标志数组和原始元素数组打印出实际的子集。
     *
     * @param flags 布尔标志数组。
     * @param items 原始集合的元素数组。
     */
    public static void dump(boolean[] flags, String[] items) {
        System.out.print("{");
        boolean firstElement = true;
        for (int i = 0; i < flags.length; ++i) {
            if (flags[i]) {
                if (!firstElement) {
                    System.out.print(", ");
                }
                System.out.print(items[i]);
                firstElement = false;
            }
        }
        System.out.println("}");
    }

    public static void main(String[] args) throws java.lang.Exception {
        String[] fruit = {"Apple", "Mango", "Banana", "Pear"};
        boolean[] flags = new boolean[fruit.length]; // 初始状态为所有false (空集)

        System.out.println("生成幂集 (按数学顺序):");
        System.out.println("--------------------");

        do {
            dump(flags, fruit); // 打印当前子集
            // dump(flags); // 可选：打印标志数组状态
        } while (advance(flags)); // 循环直到 advance 返回 false (全集已生成)
    }
}

生成幂集 (按数学顺序):
--------------------
{}
{Apple}
{Mango}
{Banana}
{Pear}
{Apple, Mango}
{Apple, Banana}
{Apple, Pear}
{Mango, Banana}
{Mango, Pear}
{Banana, Pear}
{Apple, Mango, Banana}
{Apple, Mango, Pear}
{Apple, Banana, Pear}
{Mango, Banana, Pear}
{Apple, Mango, Banana, Pear}

NNNN
YNNN
NYNN
NNYN
NNNY
YYNN
YNYN
YNNY
NYYN
NYNY
NNYY
YYYN
YYNY
YNYY
NYYY
YYYY