Scalaの範囲を均等に分割した連続する範囲に分割する

Question

範囲がある場合、どのように分割範囲（バケット）の数を指定する連続した部分範囲の列に分割できますか？十分な品物がない場合は、空のバケットを省略してください。例えば

：

splitRange(1 to 6, 3) == Seq(Range(1,2), Range(3,4), Range(5,6)) 
splitRange(1 to 2, 3) == Seq(Range(1), Range(2)) 

いくつかの追加の制約、そのルールアウトは私が見てきたソリューションの一部：

1. 大雑把にでもバケツサイズ - バケットサイズはで、1によって変化すべきですほとんど
2. 入力範囲の長さが非常に長い場合がありますので、範囲をシーケンスに具体化しないでください（groupedは使用できません）
3. これはまた、ラケットロビン方式でバケットに数値を割り当てるのではなく、各バケット内の数値が連続していないため範囲を形成しないためです。
4. 理想的には、順番に、すなわち、（1,2）、（3,4）、（3,4）、（1,2）

同僚は、溶液here見つかりません：

def splitRange(r: Range, chunks: Int): Seq[Range] = { 
    if (r.step != 1) 
     throw new IllegalArgumentException("Range must have step size equal to 1") 

    val nchunks = scala.math.max(chunks, 1) 
    val chunkSize = scala.math.max(r.length/nchunks, 1) 
    val starts = r.by(chunkSize).take(nchunks) 
    val ends = starts.map(_ - 1).drop(1) :+ r.end 
    starts.zip(ends).map(x => x._1 to x._2) 
} 

をこれが生成することができ例えば、Nが小さい場合、バケットのサイズが非常に不均一になります。例：

splitRange(1 to 14, 5)       
//> Vector(Range(1, 2), Range(3, 4), Range(5, 6), 
//|  Range(7, 8), Range(9, 10, 11, 12, 13, 14)) 
           ^^^^^^^^^^^^^^^^^^^^^ 

Answer 1

浮動小数点

一つの方法は、次に、各バケットのオフセット分数（浮動小数点数）を生成ジッピングによって、整数範囲にこれらを変換することである近づきます。空の範囲は、collectを使用して除外する必要があります。

def splitRange(r: Range, chunks: Int): Seq[Range] = { 
    require(r.step == 1, "Range must have step size equal to 1") 
    require(chunks >= 1, "Must ask for at least 1 chunk") 

    val m = r.length.toDouble 
    val chunkSize = m/chunks 
    val bins = (0 to chunks).map { x => math.round((x.toDouble * m)/chunks).toInt } 
    val pairs = bins zip (bins.tail) 
    pairs.collect { case (a, b) if b > a => a to b } 
} 

（このソリューションの最初のバージョンは、それがInt.MaxValueを扱うことができなかったように丸め問題があった - これは今すぐ下記レックスカーの再帰的な浮動小数点ソリューションに基づいて修正されました）

別の浮動小数点アプローチは、範囲を再帰させることです。毎回範囲を外れるので、要素を見逃すことはできません。このバージョンではInt.MaxValueを正しく処理できます。

def splitRange(r: Range, chunks: Int): Seq[Range] = { 
    require(r.step == 1, "Range must have step size equal to 1") 
    require(chunks >= 1, "Must ask for at least 1 chunk") 

    val chunkSize = r.length.toDouble/chunks 

    def go(i: Int, r: Range, delta: Double, acc: List[Range]): List[Range] = { 
    if (i == chunks) r :: acc 
     // ensures the last chunk has all remaining values, even if error accumulates 
    else { 
     val s = delta + chunkSize 
     val (chunk, rest) = r.splitAt(s.toInt) 
     go(i + 1, rest, s - s.toInt, if (chunk.length > 0) chunk :: acc else acc) 
    } 
    } 

    go(1, r, 0.0D, Nil).reverse 
} 

（開始、終了）ペアを生成するために、それらを圧縮するのではなく、反復することもできます。割り当てる方法 - これは整数アプローチ

最後に、私は、これは基本的に同等の問題を解決した、Bresenham's line-drawing algorithmを適合させることにより、純粋な整数演算で行うことができることを理解レックスカーのanswer to a similar question

def splitRange(r: Range, chunks: Int): Seq[Range] = { 
    require(r.step == 1, "Range must have step size equal to 1") 
    require(chunks >= 1, "Must ask for at least 1 chunk") 

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

から適合されています整数演算のみを使用して、y行にわたって均等にxピクセルを表示します。

私は当初、末尾再帰ソリューションにそれを変換し、その後、varとArrayBufferを使用して不可欠溶液の中に擬似コードを翻訳：

def splitRange(r: Range, chunks: Int): List[Range] = { 
    require(r.step == 1, "Range must have step size equal to 1") 
    require(chunks >= 1, "Must ask for at least 1 chunk") 

    val dy = r.length 
    val dx = chunks 

    @tailrec 
    def go(y0:Int, y:Int, d:Int, ch:Int, acc: List[Range]):List[Range] = { 
    if (ch == 0) acc 
    else { 
     if (d > 0) go(y0, y-1, d-dx, ch, acc) 
     else go(y-1, y, d+dy, ch-1, if (y > y0) acc 
            else (y to y0) :: acc) 
    } 
    } 

    go(r.end, r.end, dy - dx, chunks, Nil) 
} 

完全な説明については、Wikipediaのリンクを参照してください、しかし、基本的にしてくださいアルゴリズムは、線の傾きをジグザグにするか、またはy範囲をdyに追加し、x範囲をdxから差し引きます。これらが正確に分割されない場合、正確に分割されるまでエラーが累積され、一部のサブレンジでは余分なピクセルが発生します。

splitRange(3 to 15, 5)       
//> List(Range(3, 4), Range(5, 6, 7), Range(8, 9), 
//|  Range(10, 11, 12), Range(13, 14, 15))