scala - 两个列表的笛卡尔积

Question

给定一个数字与多个字符相关联的映射

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)

这里事情变得丑陋，它只适用于三位数的序列。有没有办法对任何序列长度都达到相同的结果？

Answer 1

以下建议不使用 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 的非单一元素的数量呈指数增长。