两个列表的笛卡尔积
给定一个数字与多个字符相关联的映射,
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 compressions 来执行此操作
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)
这里事情变得丑陋,它只适用于三位数字的序列。有什么方法可以对任何序列长度实现相同的结果吗?
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")
I can do this with for comprehensions
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?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
以下建议不使用 for 理解式。但我认为这毕竟不是一个好主意,因为正如您所注意到的,您将受到笛卡尔积的一定长度的限制。
为什么不采用尾递归呢?
请注意,上面的递归函数不是尾递归。这不是问题,因为
xss
会很短,除非xss
中有很多单例列表。情况确实如此,因为结果的大小随着xss
的非单一元素的数量呈指数增长。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.
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 inxss
. This is the case, because the size of the result grows exponentially with the number of non-singleton elements ofxss
.我可以想出这个:
I could come up with this:
我只是做了如下操作,它起作用了,
看不到正在处理它的 $Tree 类型也适用于任意集合。
I just did that as follows and it works
Don't see the $Tree type that am dealing it works for arbitrary collections too..