Java中使用位掩码生成集合的所有r子集（位运算高效实现）

梦磊吖_6172

发布时间：2026-05-30 18:34:35

660人浏览过

来源于php中文网

原创

Java中使用位掩码生成集合的所有r子集（位运算高效实现）

本文详解如何利用二进制位掩码（bitmask）在java中高效生成并输出给定集合s的所有r元子集，涵盖用户输入处理、掩码遍历、子集元素提取、计数与格式化输出，并附完整可运行代码。

本文详解如何利用二进制位掩码（bitmask）在java中高效生成并输出给定集合s的所有r元子集，涵盖用户输入处理、掩码遍历、子集元素提取、计数与格式化输出，并附完整可运行代码。

在组合数学与算法实践中，生成指定大小的子集（即r-子集）是一个经典问题。本教程采用位掩码（bitmask）技术——一种以整数二进制表示模拟集合成员关系的高效方法：对含n个元素的集合S，用0到2ⁿ−1之间的每个整数作为“掩码”，其第i位为1表示S中第i个元素被选入当前子集，为0则未选。该方法时间复杂度为O(n·2ⁿ)，空间复杂度仅为O(n)，避免递归或额外数据结构开销，特别适合n ≤ 10的约束条件。

核心原理：掩码如何表示子集？

假设集合S = [a₀, a₁, a₂, ..., aₙ₋₁]，掩码mask是一个n位二进制数。例如，当n=4、mask = 6（二进制0110）时，表示选取索引1和2对应的元素（a₁, a₂），构成子集{a₁, a₂}。判断第i位是否为1，使用位运算：(mask & (1 << i)) != 0；统计掩码中1的个数（即子集大小），可逐位检查或调用Integer.bitCount(mask)。

完整Java实现

以下程序严格遵循题目要求：读取集合S（最多10个互异整数）和目标大小r，使用掩码遍历所有2ⁿ个子集，筛选出大小恰好为r的子集并规范输出：

Java Maven Code Review

审查Java Maven项目（ZIP压缩包或GitLab仓库URL），检查代码规范、命名、模块边界、可维护性问题以及重复代码。

下载

import java.util.*;

public class SubsetGenerator {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        // 步骤1：获取用户输入
        System.out.print("Please enter S: ");
        String[] sTokens = input.nextLine().trim().split("\s+");
        int[] arr = new int[sTokens.length];
        for (int i = 0; i < sTokens.length; i++) {
            arr[i] = Integer.parseInt(sTokens[i]);
        }
        System.out.print("Please enter r: ");
        int r = input.nextInt();
        int n = arr.length;

        // 步骤2-4：掩码遍历 + 筛选 + 输出
        List<List<Integer>> rSubsets = new ArrayList<>();
        int total = 0;
        int allMasks = 1 << n; // 即 2^n

        System.out.println(r + "-subsets of S are the following:");
        for (int mask = 0; mask < allMasks; mask++) {
            // 统计当前掩码中1的个数（子集大小）
            int count = Integer.bitCount(mask);
            if (count != r) continue;

            // 构建并输出当前r-子集
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(arr[i]);
                }
            }
            rSubsets.add(subset);
            System.out.print("{ ");
            for (int i = 0; i < subset.size(); i++) {
                System.out.print(subset.get(i));
                if (i < subset.size() - 1) System.out.print(" ");
            }
            System.out.println(" }");
            total++;
        }

        // 步骤4：输出总数
        System.out.println("There are " + total + " r-subsets");
        input.close();
    }
}