将集合划分为"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)
}

Answer 2

典型的"最佳"分区在切割后计算精确的分数长度,然后进行舍入以找到要采用的实际数量:

def cut[A](xs: Seq[A], n: Int):Vector[Seq[A]] = {
  val m = xs.length
  val targets = (0 to n).map{x => math.round((x.toDouble*m)/n).toInt}
  def snip(xs: Seq[A], ns: Seq[Int], got: Vector[Seq[A]]): Vector[Seq[A]] = {
    if (ns.length<2) got
    else {
      val (i,j) = (ns.head, ns.tail.head)
      snip(xs.drop(j-i), ns.tail, got :+ xs.take(j-i))
    }
  }
  snip(xs, targets, Vector.empty)
}

这样,您的较长和较短的块将被穿插,这通常更适合于均匀度:

scala> cut(List(1,2,3,4,5,6,7,8,9,10),4)
res5: Vector[Seq[Int]] = 
  Vector(List(1, 2, 3), List(4, 5), List(6, 7, 8), List(9, 10))

你甚至可以削减多少元素:

scala> cut(List(1,2,3),5)
res6: Vector[Seq[Int]] = 
  Vector(List(1), List(), List(2), List(), List(3))