18

数字が複数の文字に関連付けられているマップを考える

scala> val conversion = Map("0" -> List("A", "B"), "1" -> List("C", "D"))
conversion: scala.collection.immutable.Map[java.lang.String,List[java.lang.String]] =
  Map(0 -> List(A, B), 1 -> List(C, D))

数字のシーケンスに基づいて、可能なすべての文字シーケンスを生成したいと考えています。例:

"00" -> List("AA", "AB", "BA", "BB")
"01" -> List("AC", "AD", "BC", "BD")

理解のためにこれを行うことができます

scala> val number = "011"
number: java.lang.String = 011

インデックスごとに可能な文字のシーケンスを作成します

scala> val values = number map { case c => conversion(c.toString) }
values: scala.collection.immutable.IndexedSeq[List[java.lang.String]] =
  Vector(List(A, B), List(C, D), List(C, D))

可能なすべての文字列を生成する

scala> for {
     | a <- values(0)
     | b <- values(1)
     | c <- values(2)
     | } yield a+b+c
res13: List[java.lang.String] = List(ACC, ACD, ADC, ADD, BCC, BCD, BDC, BDD)

ここで事態は悪化し、3 桁のシーケンスに対してのみ機能します。どのシーケンス長でも同じ結果を得る方法はありますか?

4

3 に答える 3

15

次の提案は、for 内包表記を使用していません。しかし、お気づきのように、デカルト積の特定の長さに縛られるので、結局は良い考えではないと思います。

scala> def cartesianProduct[T](xss: List[List[T]]): List[List[T]] = xss match {
     |   case Nil => List(Nil)
     |   case h :: t => for(xh <- h; xt <- cartesianProduct(t)) yield xh :: xt
     | }
cartesianProduct: [T](xss: List[List[T]])List[List[T]]

scala> val conversion = Map('0' -> List("A", "B"), '1' -> List("C", "D"))
conversion: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map(0 -> List(A, B), 1 -> List(C, D))

scala> cartesianProduct("01".map(conversion).toList)
res9: List[List[java.lang.String]] = List(List(A, C), List(A, D), List(B, C), List(B, D))

末尾再帰ではないのはなぜですか?

上記の再帰関数は末尾再帰ではないことに注意してください。xssに多くのシングルトン リストがない限り短いので、これは問題ではありませんxss。これは、結果のサイズが の非シングルトン要素の数とともに指数関数的に増加するためですxss。

于 2011-11-21T20:32:45.187 に答える
5

私はこれを思い付くことができました：

val conversion = Map('0' -> Seq("A", "B"), '1' -> Seq("C", "D"))

def permut(str: Seq[Char]): Seq[String] = str match {
  case Seq()  => Seq.empty
  case Seq(c) => conversion(c)
  case Seq(head, tail @ _*) =>
    val t = permut(tail)
    conversion(head).flatMap(pre => t.map(pre + _))
}

permut("011")
于 2011-11-21T20:35:41.690 に答える
-1

私はちょうどそれを次のようにしました、そしてそれは動作します

    def cross(a:IndexedSeq[Tree], b:IndexedSeq[Tree]) = {
        a.map (p => b.map( o => (p,o))).flatten
    }

任意のコレクションでも機能する $Tree タイプが表示されない..

于 2016-08-27T08:36:28.607 に答える