Scala 函数获取大小为 k 的所有排序子集

Question

我得到了一组大小为 L 的集合，并且想要生成大小为 k 的每个已排序子集。 如果你的解决方案是用 scala 编写的，那就太好了，但也许我可以自己翻译。

L = 6 和 k = 3 运行的示例应该会产生结果。

1, 2, 3
1, 2, 4
1, 2, 5
1, 2, 6
1, 3, 4
1, 3, 5
1, 3, 6
1, 4, 5
1, 4, 6
1, 5, 6
2, 3, 4
2, 3, 5
2, 3, 6
2, 4, 5
2, 4, 6
2, 5, 6
3, 4, 5
3, 4, 6
3, 5, 6
4, 5, 6

我的 scala 尝试是这样的：

object Util {
  def main(args : Array[String]) : Unit = {
    starts(6,3,1)
  }

  def starts(L: Int, num: Int, level: Int) : List[List[Int]] = {
    if( num == 0 ) {
      return List()
    }else{
      (level to (L-num+1)).map( o => o :: starts(L,num-1,level+1))
    }
  }
}

我希望你能帮助我。

Answer 1

您所需要的只是

def subsets(L: Int, k: Int) =  
  1 to L combinations k

结果：

scala> subsets(6, 3) foreach println
Vector(1, 2, 3)
Vector(1, 2, 4)
Vector(1, 2, 5)
Vector(1, 2, 6)
Vector(1, 3, 4)
Vector(1, 3, 5)
Vector(1, 3, 6)
Vector(1, 4, 5)
Vector(1, 4, 6)
Vector(1, 5, 6)
Vector(2, 3, 4)
Vector(2, 3, 5)
Vector(2, 3, 6)
Vector(2, 4, 5)
Vector(2, 4, 6)
Vector(2, 5, 6)
Vector(3, 4, 5)
Vector(3, 4, 6)
Vector(3, 5, 6)
Vector(4, 5, 6)

按要求。

Answer 2

你可以从那开始

def subsets(start: Int, end: Int, count: Int) :Seq[Seq[Int]] = (
  if (count == 0) 
    List(Nil)
  else 
    for(head <- start to end; tail <- subsets(head + 1, end, count -1)) 
    yield head +: tail
)

Answer 3

如果您实际上有块而不是条目，那么您需要知道每个块的长度。您所显示的是条目（或者等效地，长度为 1 的块）。

首先，请注意我们必须有 L>=k。其次，请注意，如果第一个条目是 i，则剩余的可能性是 i+f(Li,k-1)，其中 f 是产生条目的内容，并假设 + 分布在集合中。最后，我们注意到，带有为每个元素生成序列的函数的 flatMap 会将结果解压缩为单个序列。

现在我们已经拥有了需要知道的一切：

def choices(N: Int, k: Int): List[List[Int]] = {
  if (k==1) (1 to N).toList.map(x => List(x))
  else if (N < k) Nil
  else (1 to 1+N-k).toList.flatMap{ i =>
    choices(N-i,k-1).map(xs => i :: xs.map(_ + i))
  }
}

如果您实际上指的是块，那么我们需要知道块有多长。分析是相同的，只是我们需要跳过块大小，而不是只跳过一个值：（

def blockchoices(N: Int, k: Int, size: Int): List[List[Int]] = {
  if (k==1) (1 to N+1-size).toList.map(x => List(x))
  else if (N <= k+size) Nil
  else (1 to 2+N-k-size).toList.flatMap{ i =>
    choices(N-i+1-size, k-1, size).map(xs => i :: xs.map(_ + i+size-1))
  }
}

列出了块的起始条目）。