生成可能的布尔组合的最优雅方式

Question

如何以最优雅的方式生成给定布尔值个数下可能的所有布尔组合？

例如：

bool(1) -> [false], [true]
bool(2) -> [false, false], [false, true], [true, false], [true, true]
...

这是我的当前实现：

public static List<Boolean[]> bool(int n) {
    return IntStream.range(0, (int) Math.pow(2, n))
                    .mapToObj(i -> StringUtils.leftPad(Integer.toBinaryString(i), n, '0').chars().mapToObj(c -> c != '0').toArray(Boolean[]::new))
                    .collect(Collectors.toList());
}

然而，我对使用整数后再用StringUtils.leftPad映射到二进制以及返回Boolean[]而不是boolean[]的map功能不满意。

是否有一种更好的方法可以使用流API在一行中完成？

- user2336315

---

从零开始计数，使用整数类型作为位域？ - chrylis -cautiouslyoptimistic-

他不就是在做这个吗？将整数转换为二进制字符串，然后逐个字符转换为布尔值。 - Todd

惊讶于commons中没有这样的方法 - TheBakker

Answer 1

试试这个：

boolean[] bitSetToArray(BitSet bs, int width) {
    boolean[] result = new boolean[width]; // all false
    bs.stream().forEach(i -> result[i] = true);
    return result;
}

List<boolean[]> bool(int n) {
    return IntStream.range(0, (int)Math.pow(2, n))
        .mapToObj(i -> bitSetToArray(BitSet.valueOf(new long[] { i }), n))
        .collect(toList());
}

关键在于BitSet上有一个stream()方法，它返回一个一位的索引流。这可以用来将true值设置到boolean[]中。还要注意，（像Bubletan一样）可以使用List<boolean[]>代替List<Boolean[]>。也就是说，可以使用原始类型boolean值的数组列表，而不是装箱的Boolean值的数组列表。 （这是因为数组属于引用类型，因此可以用作类型参数。）

最后，感谢Bubletan，我通过添加bitSetToArray()来增强他的解决方案。 更新 srborlongan在评论中问是否以下内容更好：

List<boolean[]> bool(int n) {
    return IntStream.range(0, (int)Math.pow(2, n))
        .mapToObj(i -> new long[] { i })
        .map(BitSet::valueOf)
        .map(bs -> bitSetToArray(bs, n))
        .collect(toList());
}

它有一个更少密集的优点。毕竟，这不是代码高尔夫、APL或Perl，目标似乎是以最简洁的方式编写某事。代码越简单，通常情况下，阅读和理解起来就越容易。

尽管如此，在这种情况下有一些微妙之处。由“mapToObj”阶段发出的“obj”是long[]，它被推断为BitSet::valueOf的参数类型。这反过来影响了重载分辨率！除非您已经非常熟悉BitSet API，否则您必须自己进行一些类型推断才能弄清楚这是在做什么。因此，在这种情况下，直接调用BitSet.valueOf(long[])可能更好。

就性能而言——这并不总是首要任务——我认为直接方法调用可能比一系列map操作表现更好。通过额外的流操作传递一个值可能需要两次方法调用，以及附加lambda的Lambda Metafactory调用的开销。此外，与通过流传递值相比，直接方法调用很可能更容易被JIT优化和内联。但我还没有验证任何内容。

- Stuart Marks

---

将mapToObj函数拆分为.mapToObj(i -> new long[] { i }).map(BitSet::valueOf).map(bs -> bitSetToArray(bs, n))是否更好？ - srborlongan

Answer 2

尝试了一些东西。并没有完全使用Stream API.. 尽管我认为不可能用它来创建一个boolean[]。 我没有多少经验，所以我可能是错的。

public static List<boolean[]> bool(int n) {
    return IntStream.range(0, 1 << n)
            .mapToObj(i -> BitSet.valueOf(new long[] {i}))
            .map(bs -> {
                boolean[] a = new boolean[n];
                for (int i = 0; i < n; i++) {
                    a[n - i - 1] = bs.get(i);
                }
                return a;
            })
            .collect(Collectors.toList());
}

- Bubletan

Answer 3

如果必须使用“流”：

Stream：

public static List<boolean[]> bool(int n) {
    return IntStream.range(0, 1<<n).mapToObj(
        i->IntStream.range(0, n)
            .collect(()->new boolean[n], (ba,j)->ba[j]=((i>>>j)&1)!=0,
            (x,y)->{throw new UnsupportedOperationException();})
      ).collect(Collectors.toList());
}

我省略了两个boolean[]数组的未使用合并函数，虽然可以提供这样的函数。但特别是内部的Stream代码与直接循环相比并没有太大优势：

public static List<boolean[]> bool(int n) {
    return IntStream.range(0, 1<<n).mapToObj(i-> {
        boolean[] ba=new boolean[n];
        for(int j=0; j<n; j++) ba[j]=((i>>>j)&1)!=0;
        return ba;
    }).collect(Collectors.toList());
}

- Holger

Answer 4

只需要一行代码 - 它会给你一个 Iterator 而不是一个 List，但它演示了计数并将每个计数位呈现为 boolean 的原则。

public static Iterator<Boolean[]> bool(final int n) {
    return new Iterator<Boolean[]>() {
        final BigInteger max = BigInteger.ONE.shiftLeft(n);
        BigInteger next = BigInteger.ZERO;

        @Override
        public boolean hasNext() {
            return next.compareTo(max) < 0;
        }

        @Override
        public Boolean[] next() {
            Boolean[] b = new Boolean[n];
            for (int i = 0; i < n; i++) {
                b[i] = next.testBit(i);
            }
            next = next.add(BigInteger.ONE);
            return b;
        }

    };
}

OldCurmudgeon 没有时间去理会这些新潮的 Stream 东西。它们永远不会流行 - 这只是一种时尚...离开我的草坪!! :)

我对 Stream 解决方案的失败尝试 - 我仍然无法理解它们：

private static Boolean[] asBooleanArray(BigInteger n) {
    int l = n.bitLength();
    Boolean[] b = new Boolean[l];
    for (int i = 0; i < l; i++) {
        b[i] = n.testBit(i);
    }
    return b;
}

    List<Boolean[]> bools = 
            Stream.<BigInteger>iterate(
                    BigInteger.ZERO, 
                    i -> i.add(BigInteger.ONE))
            .map(n -> asBooleanArray(n))
            .collect(Collectors.toList());

我在终止一个无限的流（Stream）方面遇到了问题。

- OldCurmudgeon