algorithm - 生成所有长度为 n 的二进制字

Question

对于我目前正在实现的算法，我需要处理前面的步骤，我不完全确定它在计算上是否易于处理。此步骤需要生成所有长度为 n 的二进制字，对于任意 n(它可以很大，但实际上不应大于 50)。如果我没记错的话，这具有指数复杂度 (O(2^n))，这是不好的。

一个朴素的递归实现可能如下所示:

def gen(n: Int, acc: List[String]) : List[String] = {
  if (n == 0) {
    acc
  } else {
    if (acc.length == 0) {
      gen(n - 1, List("0", "1"))
    } else {
      gen(n - 1, (for (i <- acc) yield i ++ "0") ++ (for (j <- acc) yield j ++ "1"))
    }
  }
}
gen(4, List())  //List(0000, 1000, 0100, 1100, 0010, 1010, 0110, 1110, 0001, 1001, 0101, 1101, 0011, 1011, 0111, 1111)

这适用于较小的 n，但随着 n 的增加，我的计算机会很快死机。

这个问题也可以看作是获取所有自然数的二进制表示[0,2^n - 1]，可以很容易地并行化，但是对于大值来说无论如何都行不通n，因为元素的数量很大。

即使这是可能的，另一个问题是大多数数据结构都有大小限制(Int.MaxValue 大多数)，但那是另一回事了:)

这个问题真的有解决办法吗？

Answer 1

自 scala显然支持 BigInteger - 我对在 Scala 中编码一无所知 - 你可以简单地用它来表示那些词。剩下的很简单:
所有长度为 n 的二进制字在 [0 , 1 << n) .只需从 0 作为起始值并递增:

for (bint <- 0L until 1L << n)
    process(bint)

或

0L until (1L<<n) foreach process

这将生成所有按字典顺序匹配的单词。
更重要的问题:如果n = 40 ，您已经得到 2^40 个单词。即使您只使用 40 位 = 每个字 5 个字节，您最终也会得到总共 5TB 的数据。我怀疑您是否有能力处理那么多数据。应该有比生成该列表更好的方法。