两个列表的笛卡尔积

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

我可以使用for推导式完成这个操作

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)

这里的情况变得复杂，只适用于三位数字的序列。有没有办法实现对于任意序列长度都能获得相同的结果？

- Mark Jayxcela

---

严格来说，你所尝试获取的并不是笛卡尔积。如果你有一个 List[T]，你不能保证其大小，并且该列表应该是同质的。 - Vlad Patryshev

Answer 1

以下建议不使用for-comprehension。但是我认为这并不是一个好主意，因为正如您注意到的那样，您将被绑定到您的笛卡尔积的某个长度。

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的非单例元素数量呈指数增长。

- ziggystar

Answer 2

我可以提供以下翻译：

我可以想出这个：

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

- 0__

---

谢谢Sciss，我接受了ziggystar的答案，因为他先发了帖子，两个答案都很好。我特别喜欢你将for分解成一系列flatMaps的想法。 - Mark Jayxcela

@Mark Sciss的答案在语法上与我的不同（至少对于构建组合部分是这样）。他使用了map和flatMap，而我使用了for-comprehension语法糖，这个语法糖会被编译器转换为Sciss的代码。唯一的其他区别是我提取了一个方法来计算笛卡尔积。 - ziggystar

@ziggystar 很好，现在我更清楚地了解了幕后发生的事情。 - Mark Jayxcela

Answer 3

我刚刚按照以下方式做了，它可以正常工作

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

我处理的$Tree类型也适用于任意集合，不要误解。

- Vijay Krishna Menon