所有组合的列表

Question

我目前正在努力解决组合问题。作为初始输入，我有一个元组列表列表，换句话说如下:

List[List[(Char, Int)]]
List(List('k', 2), List('r', 2))

鉴于上面的输入，或者 char 和 int 的任意组合，我应该返回以下内容:

List(List(),List(('k', 1)),List(('k', 2)),List(('r', 1)),List(('k', 1), ('r', 1)),
     List(('k', 2), ('r', 1)), List(('r', 2)), List(('k', 1), ('r', 2)), 
     List(('k', 2), ('r', 2))
)

使用 Scala 的 For，我将字符和整数分离到列表中

List(List(), List(1), List(2), List(1, 2))
List(List(), List(k), List(r), List(k, r))

但我一直纠结于如何合并两个列表以获得上面所有子集的列表。我试过了

lettersets map (i => numsets flatMap (j => i zip j))

然而，这会返回以下不完整且不正确的结果:

List(
     List(), List((k,1), (k,2), (k,1)), List((r,1), (r,2), (r,1)), 
     List((k,1), (k,2), (r,1), (r,2))
    )

任何人都可以帮助我改进我的方法，或者告诉我为什么这行不通并提出更好的方法，以便我可以获得剩余的组合。？(

List(('a', 1), ('b', 2))
List(('a', 2), ('b', 2))

附言输入列表不仅限于两个元素，它应该能够适用于原始列表的所有 N 个元素。最后，我真的不想要解决方案本身，只是建议尝试其他事情或改进我的 map of one liner map 。

感谢大家的帮助和提示。

Answer 1

我得到了答案，谢谢@Poindextrose 的提示，它让我找到了正确的答案。这是我的解决方案

  def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match {
    case List() => List(Nil)
    case (c, n) :: others =>
       val tails = combinations(others)
       tails ::: (for {
            j <- tails
            i <- 1 to n
          } yield (c, i) :: j)