两个列表的笛卡尔积

发布于 2024-12-17 05:26:18 字数 1058 浏览 2 评论 0原文

给定一个数字与多个字符相关联的映射,

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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

本宫微胖 2024-12-24 05:26:18

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

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

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

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.

咿呀咿呀哟 2024-12-24 05:26:18

我可以想出这个:

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

I could come up with this:

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")
遮云壑 2024-12-24 05:26:18

我只是做了如下操作,它起作用了,

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

看不到正在处理它的 $Tree 类型也适用于任意集合。

I just did that as follows and it works

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

Don't see the $Tree type that am dealing it works for arbitrary collections too..

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文