如何用掩码实现Java程序生成集合S的r子集？

作业要求 #

编写程序生成并打印集合S的所有r子集，由用户提供集合S与数值r，同时输出r子集的数量。需使用掩码（mask）生成S的所有子集，再筛选出元素个数为r的子集。程序需完成：

• 提示用户输入集合S的元素及r值（S大小不超过10，元素无重复）；
• 用掩码生成S的所有子集；
• 筛选并输出元素个数为r的子集；
• 输出r子集总数。

示例交互 #

Please enter S: 1 2 3 4 5 6
Please enter r: 4
4-subsets of S are the following:
{ 1 2 3 4 }
{ 1 2 3 5 }
{ 1 2 4 5 }
{ 1 3 4 5 }
{ 2 3 4 5 }
{ 1 2 3 6 }
{ 1 2 4 6 }
{ 1 3 4 6 }
{ 2 3 4 6 }
{ 1 2 5 6 }
{ 1 3 5 6 }
{ 2 3 5 6 }
{ 1 4 5 6 }
{ 2 4 5 6 }
{ 3 4 5 6 }
There are 15 r-subsets

现有错误代码 #

用户原代码未实现掩码逻辑，且存在语法错误（func方法中未定义变量i），无法完成需求：

import java.util.*;
import java.util.Scanner;

public class Main {

  public static void func(int[] ARR, int s, int R) {
           for (int j = i + 1; j <= R; j++) {
               System.out.println(ARR[i] + " " + ARR[j]);
           }
  }
  
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Size of set S: ");
    int S = input.nextInt();
    int[] arr = new int[S];    
    System.out.print("Values of set S: ");
    for (int i = 0; i < S; i++) {
      arr[i] = input.nextInt();
    }
    System.out.print("Value of r: ");
    int r = input.nextInt();
    func(arr, S, r);
  }
}

修改后的完整实现（掩码方式） #

核心思路 #

掩码本质是用二进制数表示子集：对于大小为n的集合，遍历从0到2^n - 1的所有整数，每个整数的二进制位对应集合中元素的选中状态——某一位为1则选中对应位置的元素，为0则不选。统计每个掩码中1的个数，等于r时即为目标子集。

代码实现 #

import java.util.Scanner;

public class Main {

    public static void generateRSubsets(int[] set, int r) {
        int n = set.length;
        int count = 0;
        System.out.printf("%d-subsets of S are the following:\n", r);

        // 遍历所有可能的掩码：从0到2^n - 1
        for (int mask = 0; mask < (1 << n); mask++) {
            // 统计当前掩码中1的个数
            int bitCount = Integer.bitCount(mask);
            if (bitCount == r) {
                count++;
                // 输出当前子集
                System.out.print("{ ");
                for (int i = 0; i < n; i++) {
                    // 检查第i位是否为1
                    if ((mask & (1 << i)) != 0) {
                        System.out.print(set[i] + " ");
                    }
                }
                System.out.println("}");
            }
        }

        System.out.println("There are " + count + " r-subsets");
    }

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

        System.out.print("Please enter S: ");
        // 读取整行输入，分割成元素数组
        String[] elements = input.nextLine().trim().split("\\s+");
        int[] set = new int[elements.length];
        for (int i = 0; i < elements.length; i++) {
            set[i] = Integer.parseInt(elements[i]);
        }

        System.out.print("Please enter r: ");
        int r = input.nextInt();

        generateRSubsets(set, r);
        input.close();
    }
}

关键代码解释 #

1. 掩码遍历：for (int mask = 0; mask < (1 << n); mask++)，1 << n等价于2^n，遍历所有可能的子集状态。
2. 统计1的个数：Integer.bitCount(mask)直接返回掩码中二进制1的数量，快速判断是否为r子集。
3. 筛选元素：(mask & (1 << i)) != 0检查掩码的第i位是否为1，若是则将集合中第i个元素加入当前子集。
4. 输入处理：改为读取整行输入集合元素，更贴近示例交互的输入方式。

内容的提问来源于stack exchange，提问作者Zaynab B.