List("A", "B"), "1" -> List("C", "D")) conv-6ren">
gpt4 book ai didi

scala - 两个列表的笛卡尔积

转载 作者:行者123 更新时间:2023-12-02 23:05:47 26 4
gpt4 key购买 nike

给定一个地图,其中一个数字与几个字符相关联

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)


在这里情况变得很丑陋,并且仅适用于三位数的序列。有什么方法可以在任何序列长度上实现相同的结果?

最佳答案

以下建议不使用理解。但我认为这毕竟不是一个好主意,因为正如您所注意到的,您将被绑定到一定长度的笛卡尔积。

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

关于scala - 两个列表的笛卡尔积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8217764/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com