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

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 和 map 映射到二进制 returns 一个 Boolean[] 而不是boolean[].

有没有更好的方法可以使用 Stream API 在单行中做到这一点？

Answer 1

只有种单行 - 它给你一个 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。

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());
}

Answer 3

试试这个：

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() 方法 returns 一个位的索引流。这可用于将 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 Metafactory 调用额外的 lambda 的开销。此外，与通过流传递值相比，直接方法调用可能更容易被 JIT 优化和内联。但我还没有验证任何这些。

Answer 4

如果必须是Streams:

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());
}

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

Most elegant way to generate possible boolean combinations

java

java-8

java-stream