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

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

I hope you can help me.

- peri4n

---

希望你能自己解决问题，因为我不知道你想要什么，而且听起来像是作业。 - Kim Stebel

这不是作业。我只是想学习一种Scala的解决方法来解决这个问题。 - peri4n

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)

按照要求。

- Luigi Plinge

---

我认为作为一名Scala程序员，应该熟悉这个库。 :D - peri4n

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
)

- Didier Dupont

Answer 3

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

首先，请注意我们必须有L>=k。 其次，请注意，如果第一个条目为i，剩余的可能性是i+f(L-i,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))
  }
}

（块的起始条目已列出）。

- Rex Kerr

---

很好的补充。我也对这个解决方案感兴趣。不幸的是，将其推广到可变长度的块会使我的统计模型复杂度爆炸。 - peri4n