algorithm - 将集合划分为 "k"接近相等的部分(Scala，但与语言无关)

Question

在此代码块之前定义:

• dataset 可以是 Vector 或 List
• numberOfSlices 是一个 Int 表示切片数据集的“次数”

我想将数据集拆分为 numberOfSlices 个切片，尽可能均匀分布。 “拆分”我想我的意思是“分区”(所有的交集应该是空的，所有的并集应该是原始的)使用集合论术语，虽然这不一定是一个集合，只是一个任意集合。

例如

dataset = List(1, 2, 3, 4, 5, 6, 7)
numberOfSlices = 3
slices == ListBuffer(Vector(1, 2), Vector(3, 4), Vector(5, 6, 7))

有没有比我下面的方法更好的方法？ (我什至不确定这是最佳的......) 或者这可能不是算法上可行的尝试，在这种情况下是否有任何已知的好的启发式方法？

val slices = new ListBuffer[Vector[Int]]
val stepSize = dataset.length / numberOfSlices
var currentStep = 0
var looper = 0
while (looper != numberOfSlices) {
  if (looper != numberOfSlices - 1) {
    slices += dataset.slice(currentStep, currentStep + stepSize)
    currentStep += stepSize
  } else {
    slices += dataset.slice(currentStep, dataset.length)
  }
  looper += 1
}

Answer 1

如果 xs.grouped(xs.size/n) 的行为对您不起作用，则可以很容易地准确定义您想要的内容。商是小块的大小，余数是大块的个数:

def cut[A](xs: Seq[A], n: Int) = {
  val (quot, rem) = (xs.size / n, xs.size % n)
  val (smaller, bigger) = xs.splitAt(xs.size - rem * (quot + 1))
  smaller.grouped(quot) ++ bigger.grouped(quot + 1)
}