scala - 返回嵌套列表的所有组合

Question

我有以下数据结构

val list = List(1,2,
List(3,4),
List(5,6,7)
)

我想得到这个结果

List(
List(1,2,3,5), List(1,2,3,6), List(1,2,3,7),
List(1,2,4,5), List(1,2,4,6), List(1,2,4,7)
)

输入中的子列表数量和其中的元素数量可以变化

附言

我正在尝试将其用作第一步

list.map{
  case x => List(x)
  case list:List => list
}

还有一些用于理解，但它不会起作用，因为我不知道结果的每个子列表将包含多少个元素

Answer 1

像 List[Any] 这样的类型在 Scala 中最常被避免——语言的大部分功能来自于它的智能类型系统，而这种类型阻碍了这一点。因此，将列表转换为规范化 List[List[Int]] 的本能是正确的:

val normalizedList = list.map { 
    case x: Int => List(x)
    case list: List[Int @unchecked] => list 
}

请注意，如果 list 包含 Int 以外的某种类型的 List，例如 ，这最终将引发运行时异常List[String]，由于类型删除。这正是未能使用强类型时出现的那种问题!您可以阅读更多关于处理类型删除的策略 here .

一旦您有了规范化的 List[List[Int]]，您就可以使用 foldLeft 来构建组合。您也正确地看到 for 理解在这里可以很好地工作:

normalizedList.foldLeft(List(List.empty[Int])) { (acc, next) => 
    for { 
        combo <- acc
        num <- next 
    } yield (combo :+ num) 
}

在 foldLeft 的每次迭代中，我们都会考虑来自 normalizedList 的另一个子列表 (next)。我们查看到目前为止构建的每个组合(acc 中的每个 combo)，然后查看 next 中的每个数字 num >，我们通过将其附加到 combo 来创建一个新组合。

正如您现在可能看到的那样，for 理解实际上是 map、flatMap 和 filter 操作的语法糖.所以我们也可以用那些更原始的方法来表达:

normalizedList.foldLeft(List(List.empty[Int])) { (acc, next) => 
    acc.flatMap { combo => 
        next.map { num => combo :+ num } 
    } 
}

您甚至可以为 foldLeft 使用(有点傻):/ 别名，切换 map 的顺序，并使用下划线语法来实现极致简洁:

(List(List[Int]()) /: normalizedList) { (acc, next) => next.flatMap { num => acc.map(_ :+ num) } }