scala - ¿Cómo convertir el algoritmo de retroceso a la transmisión?

stream backtracking

Question

¿Hay alguna manera de definir una stream con un algoritmo de backtracking en Scala?

Por ejemplo, el siguiente algoritmo de backtracking imprime todas las cadenas "binarias" de un tamaño dado.

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

Creo que puedo definir una stream de cadenas "binarias" de un tamaño dado usando otro algoritmo iterativo. Sin embargo, me pregunto si puedo convertir el algoritmo de retroceso anterior en una stream .

Answer 1

Esto es bastante sencillo:

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

Tenga en cuenta el uso de append : este método no es estándar para otras colecciones, que es un requisito porque debe tomar su parámetro por nombre.

Answer 2

Puedes, pero no va a evaluar perezosamente:

def bin(s: String, n: Int): Stream[String] = {
if (s.length == n) {
println("got " + s) // for figuring out when it''s evaluated
Stream(s)
} else {
val s0 = s + ''0''
val s1 = s + ''1''
bin(s0, n) ++ bin(s1, n)
}
}

Por ejemplo, al ejecutar bin("", 2).take(2).foreach(println) , obtendrá el siguiente resultado:

scala> bin("", 2).take(2).foreach(println)
got 00
got 01
got 10
got 11
00
01

Si no le importa usar TraversableView , puede usar la conversión que se describe aquí https://.com/a/3816012/257449 . Entonces el código se convierte en:

def toTraversable[T]( func : (T => Unit) => Unit) = new Traversable[T] {
def foreach[X]( f : T => X) = func(f(_) : Unit)
}
def bin2(str: String, n: Int) = {
def recurse[U](s: String, f: (String) => U) {
if (s.length == n) {
println("got " + s) // for figuring out when it''s evaluated
f(s)
} else {
recurse(s + ''0'', f)
recurse(s + ''1'', f)
}
}
toTraversable[String](recurse(str, _)) view
}

Entonces

scala> bin2("", 2).take(2).foreach(println)
got 00
00
got 01
01
got 10