# Scala function to get all sorted subsets of size k

I am given a set of size L and want to generate every sorted subset of size k. Would be great if your solution is in scala but maybe I am able to translate by myself.

An example run for L = 6 and k = 3 should yield.

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

My scala attempt was something like:

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.

## Answers

You could start from that

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 )

All you need is

def subsets(L: Int, k: Int) = 1 to L combinations k

Results:

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)

as required.

If you actually have *blocks* and not *entries* then you need to know how long each block is. What you've shown is for entries (or, equivalently, blocks of length 1).

First, note that we must have L>=k. Second, note that if the first entry is i, the remaining possibilities are i+f(L-i,k-1), where f is what produces the entries, and assuming that + distributes across collections. Finally, we note that a flatMap with a function that produces sequences for every element will unpack the result into a single sequence.

Now that we have everything we need to know:

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

If you did in fact mean blocks, then we need to know how long the blocks are. The analysis is the same, except instead of skipping only one value, we need to skip the block size:

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

(the starting entry of the block is listed).