# 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.

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

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