如何将回溯算法转换为流？

Question

有没有办法在Scala中定义stream一个backtracking算法？

例如,以下backtracking算法打印给定大小的所有"二进制"字符串.

def binaries(s:String, n:Int) {
  if (s.size == n)
    println(s)
  else {
    binaries(s + '0', n)
    binaries(s + '1', n)
  }
}

我相信我可以stream使用另一种迭代算法定义一个给定大小的"二进制"字符串.不过我想知道我是否可以将上面的回溯算法转换为stream.

Answer 1

这很简单:

def binaries(s: String, n: Int): Stream[String] = 
  if (s.size == n) Stream(s) 
  else binaries(s + "0", n) append binaries(s + "1", n)

注意使用append- 此方法对于其他集合是非标准的,这是一个要求,因为它必须按名称获取其参数.