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


Need Your Help

PHP retrieve array of items from a multidimensional array without looping?

php arrays loops multidimensional-array for-loop

I have a large array of arrays and each of these sub-arrays has an ID and some other info. Is there a way to access an array of just the ID's without using a loop?

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.