分區的集合到「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

由於Kaito提到grouped正是你所期待的。但是如果你只是想知道如何實現這種方法，有很多方法;-)。例如，你可以做這樣的：

def grouped[A](xs: List[A], size: Int) = { 
    def grouped[A](xs: List[A], size: Int, result: List[List[A]]): List[List[A]] = { 
    if(xs.isEmpty) { 
     result 
    } else { 
     val (slice, rest) = xs.splitAt(size) 
     grouped(rest, size, result :+ slice) 
    } 
    } 
    grouped(xs, size, Nil) 
} 

Answer 3

我接近這樣說：給定n元素和m分區（N> M），是n mod m == 0，在這種情況下，每個分區將有n/m個元素，或者n mod m = y，在這種情況下，每個分區將包含n/m元素，並且您必須通過m分配y。

您將有y插槽與n/m+1元素和（m-y）插槽與n/m。你如何分配它們是你的選擇。

Answer 4

典型的「最佳」分切後計算出精確的分數的長度，然後四捨五入找到實際數量取：

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

Answer 5

這是一個單線程，爲我完成這項工作，使用熟悉的Scala技巧遞歸函數返回Stream。注意使用(x+k/2)/k來四捨五入大小，插入最終列表中的較小和較大的塊，所有大小都至多有一個差異元素。如果用四捨五入的方法取代(x+k-1)/k，則將較小的塊移到末尾，x/k將它們移動到開頭。

def k_folds(k: Int, vv: Seq[Int]): Stream[Seq[Int]] = 
    if (k > 1) 
     vv.take((vv.size+k/2)/k) +: k_folds(k-1, vv.drop((vv.size+k/2)/k)) 
    else 
     Stream(vv) 

演示：

scala> val indices = scala.util.Random.shuffle(1 to 39) 

scala> for (ff <- k_folds(7, indices)) println(ff) 
Vector(29, 8, 24, 14, 22, 2) 
Vector(28, 36, 27, 7, 25, 4) 
Vector(6, 26, 17, 13, 23) 
Vector(3, 35, 34, 9, 37, 32) 
Vector(33, 20, 31, 11, 16) 
Vector(19, 30, 21, 39, 5, 15) 
Vector(1, 38, 18, 10, 12) 

scala> for (ff <- k_folds(7, indices)) println(ff.size) 
6 
6 
5 
6 
5 
6 
5 

scala> for (ff <- indices.grouped((indices.size+7-1)/7)) println(ff) 
Vector(29, 8, 24, 14, 22, 2) 
Vector(28, 36, 27, 7, 25, 4) 
Vector(6, 26, 17, 13, 23, 3) 
Vector(35, 34, 9, 37, 32, 33) 
Vector(20, 31, 11, 16, 19, 30) 
Vector(21, 39, 5, 15, 1, 38) 
Vector(18, 10, 12) 

scala> for (ff <- indices.grouped((indices.size+7-1)/7)) println(ff.size) 
6 
6 
6 
6 
6 
6 
3 

通知grouped怎麼不嘗試拉平所有子列表的大小。