6

Scala のアルゴリズムで streamaを定義する方法はありますか?backtracking

たとえば、次のbacktrackingアルゴリズムは、指定されたサイズのすべての「バイナリ」文字列を出力します。

def binaries(s:String, n:Int) {
  if (s.size == n)
    println(s)
  そうしないと {
    バイナリ(s + '0', n)
    バイナリ(s + '1', n)
  }
}

別の反復アルゴリズムstreamを使用して、特定のサイズの「バイナリ」文字列を定義できると思います。ただし、上記のバックトラッキングアルゴリズムを.stream

4

2 に答える 2

11

これは非常に簡単です。

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-- このメソッドは、他のコレクションでは非標準です。これは、パラメーターを名前で受け取る必要があるため、必須です。

于 2011-12-24T21:55:53.140 に答える
3

できますが、遅延評価はしません:

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

たとえば、 を実行するbin("", 2).take(2).foreach(println)と、次の出力が得られます。

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

を使用してもかまわない場合はTraversableView、ここで説明されている変換を使用できますhttps://stackoverflow.com/a/3816012/257449。したがって、コードは次のようになります。

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
}

それで

scala> bin2("", 2).take(2).foreach(println)
got 00
00
got 01
01
got 10
于 2011-12-24T20:16:46.627 に答える