Scala function to get all sorted subsets of size k

Question

I am given a set of sizes L and I want to generate each sorted subset of size k. It would be great if your solution is in scala, but maybe I can translate it myself.

An example for L = 6 and k = 3 should give.

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 this:

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 help me.

Answer 1

You can start with this

 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 ) 

Answer 2

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

Answer 3

If you actually have blocks, not records, you need to know how long each block is. What did you specify for the records (or, equivalently, blocks of length 1).

First, note that we must have L>=k . Secondly, note that if the first record is i , the remaining possibilities are i+f(Li,k-1) , where f is what produces the records, and it is assumed that + distributed across collections. Finally, note that a flatMap with a function that creates sequences for each element will decompress the result into one 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+Nk).toList.flatMap{ i => choices(Ni,k-1).map(xs => i :: xs.map(_ + i)) } } 

If you actually made middle blocks, then we need to know how long the blocks will be. The analysis is the same, except that 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+Nk-size).toList.flatMap{ i => choices(N-i+1-size, k-1, size).map(xs => i :: xs.map(_ + i+size-1)) } } 

(the initial block record is displayed).