scala – 两个列表的笛卡尔乘积

发布时间：2020-12-16 09:23:26 所属栏目：安全来源：网络整理

导读：给定一个数字与几个字符相关联的地图 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)) 我想基于一系列数字

给定一个数字与几个字符相关联的地图

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,List(C,D),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)

这里的事情变得丑陋,只能用于三位数的序列.有没有办法为任何序列长度实现相同的结果？

解决方法

以下建议不是用于理解.但是我根本不认为这是一个好主意,因为你注意到你会被束缚在一定的笛卡尔乘积上.

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",'1' -> List("C","D"))
conversion: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map(0 -> List(A,D))

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

为什么不是尾递归？

请注意,以上递归函数不是尾递归的.这不是一个问题,因为xss将很短,除非你在xss中有很多单例列表.情况就是这样,因为结果的大小与xss的非单例元素的数目呈指数增长.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!