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

Question

有什么方法可以在Scala中使用stream算法定义backtracking？

例如，以下backtracking算法将打印给定大小的所有“二进制”字符串。

def binaries(s:String，n:Int){
如果(s.size == n)
打印信息
别的 {
二进制文件(s +'0'，n)
二进制文件(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的使用-此方法对于其他集合是非标准的，这是必需的，因为它必须使用其参数名。