Integer partitioning in Scala

Question

Given n ( say 3 people ) and s ( say 100$ ), we'd like to partition s among n people.

So we need all possible n-tuples that sum to s

My Scala code below:

def weights(n:Int,s:Int):List[List[Int]] = {
     List.concat( (0 to s).toList.map(List.fill(n)(_)).flatten, (0 to s).toList).
     combinations(n).filter(_.sum==s).map(_.permutations.toList).toList.flatten
}

println(weights(3,100))

This works for small values of n. ( n=1, 2, 3 or 4).

Beyond n=4, it takes a very long time, practically unusable.

I'm looking for ways to rework my code using lazy evaluation/ Stream.

My requirements : Must work for n upto 10.

Warning : The problem gets really big really fast. My results from Matlab -

---For s =100, n = 1 thru 5 results are ---
n=1 :1 combinations
n=2 :101 combinations
n=3 :5151 combinations
n=4 :176851 combinations
n=5: 4598126 combinations
---

Answer 1

You need dynamic programming, or memoization. Same concept, anyway.

Let's say you have to divide s among n. Recursively, that's defined like this:

def permutations(s: Int, n: Int): List[List[Int]] = n match {
  case 0 => Nil
  case 1 => List(List(s))
  case _ => (0 to s).toList flatMap (x => permutations(s - x, n - 1) map (x :: _))
}

Now, this will STILL be slow as hell, but there's a catch here... you don't need to recompute permutations(s, n) for numbers you have already computed. So you can do this instead:

val memoP = collection.mutable.Map.empty[(Int, Int), List[List[Int]]]
def permutations(s: Int, n: Int): List[List[Int]] = {
  def permutationsWithHead(x: Int) = permutations(s - x, n - 1) map (x :: _)

  n match {
    case 0 => Nil
    case 1 => List(List(s))
    case _ => 
      memoP getOrElseUpdate ((s, n), 
                             (0 to s).toList flatMap permutationsWithHead)
  }
}

And this can be even further improved, because it will compute every permutation. You only need to compute every combination, and then permute that without recomputing.

To compute every combination, we can change the code like this:

val memoC = collection.mutable.Map.empty[(Int, Int, Int), List[List[Int]]]
def combinations(s: Int, n: Int, min: Int = 0): List[List[Int]] = {
  def combinationsWithHead(x: Int) = combinations(s - x, n - 1, x) map (x :: _)

  n match {
    case 0 => Nil
    case 1 => List(List(s))
    case _ => 
      memoC getOrElseUpdate ((s, n, min), 
                             (min to s / 2).toList flatMap combinationsWithHead)
  }
}

Running combinations(100, 10) is still slow, given the sheer numbers of combinations alone. The permutations for each combination can be obtained simply calling .permutation on the combination.