如何实现Java的getAllCombos方法生成指定布尔组合的SampleForSO列表？

需求说明 #

需要实现SampleForSO类的静态方法getAllCombos，满足：

• 当传入3个true和5个false时，返回的List<SampleForSO>包含：
  • 1个全选所有true的实例
  • 3种“三选二”的布尔组合实例
  • 3种“三选一”的布尔组合实例
  • 1个全false的实例
• 方法需适配任意布尔输入，即无论传入多少个true和false，都能生成从全选true到全false的所有“选k个true”的组合（k从输入中true的总数递减到0）。

实现思路 #

1. 先统计输入布尔数组中true的总数量countTrue；
2. 遍历k值从countTrue到0：
   • 对每个k，生成所有“从输入的布尔位置中选k个位置设为true，其余为false”的组合；
   • 每个组合对应创建一个SampleForSO实例；
3. 收集所有实例并返回。

核心是实现“选k个位置”的组合生成逻辑，这里用回溯法来生成所有合法的位置组合，再构建对应的布尔数组。

代码实现 #

SampleForSO类定义 #

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

public class SampleForSO {
    private final boolean[] flags;

    public SampleForSO(boolean[] flags) {
        this.flags = flags.clone(); // 避免外部修改内部数组
    }

    public boolean[] getFlags() {
        return flags.clone(); // 返回副本，保证封装性
    }

    // 重写equals和hashCode，方便测试验证
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        SampleForSO that = (SampleForSO) o;
        return java.util.Arrays.equals(flags, that.flags);
    }

    @Override
    public int hashCode() {
        return java.util.Arrays.hashCode(flags);
    }

    // 静态方法：生成所有符合要求的组合
    public static List<SampleForSO> getAllCombos(boolean[] input) {
        List<SampleForSO> result = new ArrayList<>();
        if (input == null || input.length == 0) {
            return result;
        }

        int countTrue = 0;
        for (boolean b : input) {
            if (b) countTrue++;
        }

        // 从选countTrue个true，递减到选0个（全false）
        for (int k = countTrue; k >= 0; k--) {
            // 生成所有选k个位置的组合
            List<int[]> positionCombos = generatePositionCombos(input.length, k);
            for (int[] positions : positionCombos) {
                boolean[] comboFlags = new boolean[input.length];
                // 将选中的位置设为true
                for (int pos : positions) {
                    comboFlags[pos] = true;
                }
                result.add(new SampleForSO(comboFlags));
            }
        }

        return result;
    }

    // 辅助方法：生成从n个位置中选k个的所有组合（位置索引从0开始）
    private static List<int[]> generatePositionCombos(int n, int k) {
        List<int[]> result = new ArrayList<>();
        backtrack(n, k, 0, new int[k], 0, result);
        return result;
    }

    // 回溯法生成组合
    private static void backtrack(int n, int k, int start, int[] current, int currentIndex, List<int[]> result) {
        if (currentIndex == k) {
            result.add(current.clone());
            return;
        }
        for (int i = start; i < n; i++) {
            current[currentIndex] = i;
            backtrack(n, k, i + 1, current, currentIndex + 1, result);
        }
    }
}

JUnit测试用例 #

import org.junit.jupiter.api.Test;
import java.util.List;
import static org.junit.jupiter.api.Assertions.*;

public class SampleForSOTest {

    @Test
    void testThreeTrueFiveFalse() {
        boolean[] input = {true, true, true, false, false, false, false, false};
        List<SampleForSO> combos = SampleForSO.getAllCombos(input);

        // 验证总数：1（全选）+3（三选二）+3（三选一）+1（全false）=8
        assertEquals(8, combos.size());

        // 验证全true实例存在
        boolean[] allTrue = {true, true, true, false, false, false, false, false};
        assertTrue(combos.contains(new SampleForSO(allTrue)));

        // 验证全false实例存在
        boolean[] allFalse = new boolean[8];
        assertTrue(combos.contains(new SampleForSO(allFalse)));

        // 验证三选二的组合数量（C(3,2)=3）
        int twoTrueCount = 0;
        for (SampleForSO combo : combos) {
            int trueCount = 0;
            for (boolean b : combo.getFlags()) {
                if (b) trueCount++;
            }
            if (trueCount == 2) twoTrueCount++;
        }
        assertEquals(3, twoTrueCount);

        // 验证三选一的组合数量（C(3,1)=3）
        int oneTrueCount = 0;
        for (SampleForSO combo : combos) {
            int trueCount = 0;
            for (boolean b : combo.getFlags()) {
                if (b) trueCount++;
            }
            if (trueCount == 1) oneTrueCount++;
        }
        assertEquals(3, oneTrueCount);
    }

    @Test
    void testTwoTrueTwoFalse() {
        boolean[] input = {true, true, false, false};
        List<SampleForSO> combos = SampleForSO.getAllCombos(input);

        // 总数：C(2,2)+C(2,1)+C(2,0)=1+2+1=4
        assertEquals(4, combos.size());

        int twoTrueCount = 0;
        int oneTrueCount = 0;
        int zeroTrueCount = 0;
        for (SampleForSO combo : combos) {
            int count = 0;
            for (boolean b : combo.getFlags()) if (b) count++;
            if (count == 2) twoTrueCount++;
            else if (count == 1) oneTrueCount++;
            else if (count == 0) zeroTrueCount++;
        }
        assertEquals(1, twoTrueCount);
        assertEquals(2, oneTrueCount);
        assertEquals(1, zeroTrueCount);
    }

    @Test
    void testEmptyInput() {
        List<SampleForSO> combos = SampleForSO.getAllCombos(new boolean[0]);
        assertTrue(combos.isEmpty());
    }
}

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