两个列表的笛卡尔积 [英] Cartesian product of two lists
问题描述
给出一个将数字与多个字符相关联的地图
Given a map where a digit is associated to several characters
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))
我想基于数字序列生成所有可能的字符序列.例子:
I want to generate all possible character sequences based on a sequence of digits. Examples:
"00" -> List("AA", "AB", "BA", "BB")
"01" -> List("AC", "AD", "BC", "BD")
我可以做到这一点
scala> val number = "011"
number: java.lang.String = 011
为每个索引创建可能的字符序列
Create a sequence of possible characters per index
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))
生成所有可能的字符序列
Generate all the possible character sequences
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)
在这里情况变得很丑陋,并且仅适用于三位数的序列.有什么方法可以在任何长度的序列上达到相同的结果吗?
Here things get ugly and it will only work for sequences of three digits. Is there any way to achieve the same result for any sequence length?
推荐答案
以下建议不使用理解.但我认为这毕竟不是一个好主意,因为正如您所注意到的,您将被束缚在一定长度的笛卡尔积上.
The following suggestion is not using a for-comprehension. But I don't think it's a good idea after all, because as you noticed you'd be tied to a certain length of your cartesian product.
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
的非单个元素的数量呈指数增长.
Why not tail-recursive?
Note that above recursive function is not tail-recursive. This isn't a problem, as xss
will be short unless you have a lot of singleton lists in xss
. This is the case, because the size of the result grows exponentially with the number of non-singleton elements of xss
.
这篇关于两个列表的笛卡尔积的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!