如何在Java中按数学顺序打印字符串数组的幂集？

问题描述 #

集合{1, 2, 3}的幂集按数学标准顺序应为：

{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

我定义了如下Java字符串数组（注：原代码存在语法错误，已修正）：

// 直接初始化数组的正确方式
String[] elements = {"apple", "mango", "banana"};
// 或从字符串分割生成数组的方式
String elementsStr = "apple,mango,banana";
String[] set = elementsStr.split("[ ,]+");

我尝试用位操作法打印幂集，但无法得到符合上述数学顺序的结果，我的位操作代码如下：

static void printPowerSet(String[] set) {
    long pset = (long) Math.pow(2, set.length);
    System.out.print("Power Set is \n{");
    for (int i = 0; i < pset; i++) {
        System.out.print("{");
        for (int j = 0; j < set.length; j++) {
            if ((i & (1 << j)) > 0){
                System.out.print(set[j] + " ");
            }
            if (i == 0 && j==0 )
                System.out.print(" ");
        }
        System.out.println("}");
    }
    System.out.println(" } \n");
}

问题分析 #

原位操作法的遍历逻辑是按二进制数从0到2^n-1的数值递增顺序，对应的子集顺序是按二进制位的数值排序，而非按子集元素个数升序+同个数内元素组合顺序排列。比如3个元素的场景下，原代码输出顺序为：
{}, {apple}, {mango}, {apple mango}, {banana}, {apple banana}, {mango banana}, {apple mango banana}
这和要求的数学顺序（先空集，再所有单元素子集，接着所有双元素子集，最后全集）不符。

解决方案 #

要实现数学顺序的幂集输出，需按子集元素个数从小到大遍历，对每个元素个数k（从0到数组长度），生成所有包含k个元素的子集，且子集内元素保持原数组的顺序。

实现代码 #

以下提供两种可行实现方式：

方式一：回溯生成指定大小的子集

import java.util.ArrayList;
import java.util.List;

public class OrderedPowerSet {
    public static void main(String[] args) {
        String[] set = {"apple", "mango", "banana"};
        printOrderedPowerSet(set);
    }

    static void printOrderedPowerSet(String[] set) {
        System.out.println("Power Set is");
        System.out.print("{");

        // 遍历所有子集大小：0到数组长度
        for (int k = 0; k <= set.length; k++) {
            List<List<String>> subsets = generateKSizeSubsets(set, k);
            for (List<String> subset : subsets) {
                System.out.print("{");
                for (int i = 0; i < subset.size(); i++) {
                    if (i > 0) {
                        System.out.print(", ");
                    }
                    System.out.print(subset.get(i));
                }
                System.out.print("}, ");
            }
        }
        // 移除末尾多余的逗号和空格，补全闭合大括号
        System.out.println("\b\b}");
    }

    // 生成所有包含k个元素的子集，保持元素顺序
    static List<List<String>> generateKSizeSubsets(String[] set, int k) {
        List<List<String>> result = new ArrayList<>();
        backtrack(set, k, 0, new ArrayList<>(), result);
        return result;
    }

    static void backtrack(String[] set, int k, int start, List<String> current, List<List<String>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < set.length; i++) {
            current.add(set[i]);
            backtrack(set, k, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

方式二：修正位操作法的输出顺序

如果坚持使用位操作，可以先按子集元素个数筛选掩码，再按组输出：

public class OrderedPowerSetBitwise {
    public static void main(String[] args) {
        String[] set = {"apple", "mango", "banana"};
        printOrderedPowerSetBitwise(set);
    }

    static void printOrderedPowerSetBitwise(String[] set) {
        int n = set.length;
        System.out.println("Power Set is");
        System.out.print("{");

        // 按子集元素个数分组输出
        for (int count = 0; count <= n; count++) {
            // 遍历所有可能的位掩码
            for (int mask = 0; mask < (1 << n); mask++) {
                if (Integer.bitCount(mask) == count) {
                    System.out.print("{");
                    boolean firstElement = true;
                    for (int j = 0; j < n; j++) {
                        if ((mask & (1 << j)) != 0) {
                            if (!firstElement) {
                                System.out.print(", ");
                            }
                            System.out.print(set[j]);
                            firstElement = false;
                        }
                    }
                    System.out.print("}, ");
                }
            }
        }
        System.out.println("\b\b}");
    }
}

代码说明 #

1. 回溯法：通过递归回溯生成指定大小的所有子集，严格保证子集内元素顺序与原数组一致，且按子集大小升序输出，完全匹配数学顺序。
2. 修正位操作法：先按子集元素个数筛选符合条件的位掩码，再输出对应子集，同样能得到正确顺序，但效率略低于回溯法（需遍历所有掩码再筛选）。

内容的提问来源于stack exchange，提问作者Prashant Singh