Distinct sums of integers

I need to get the distinct sums of naturals of a natural

What I came up with is:

type Sum = Stream[Int] //should maintain the invariant that
//* all Ints are positive
//* is non-strictly decreasing
//* is non-empty

def makesums(i: Int): Stream[Sum] = {

/* Schmear will try to "schmear" a sum by decreasing the first number by one,
and adding one again in the first position that won't violate the above invariants.
This is possible when the stream is not all 1's, and the above invariants are met for
the argument.

returns an Option[Sum], which is Some(schmeared) if the above is possible,
and None otherwise.
*/

def schmear(sum: Sum): Option[Sum] = sum match {
//if we can decrease the head and increase the next element while
//staying ordered, do that
case head #:: s #:: tail if (head - 1 >= s + 1) =>
Some((head - 1) #:: (s + 1) #:: tail)

//otherwise, if the head is only one larger than the second element, do the same,
//but smear the tail, restoring the invariant
case head #:: s #:: tail if head > s =>
schmear((s + 1) #:: tail).map(nt => (head - 1) #:: nt)

//otherwise, if there are at least two elements, just schmear the tail,
//and keep the orignal head
case head #:: s #:: tail =>
schmear(s #:: tail).map(nt => head #:: nt)

//otherwise, if the head is larger than 1, decrease by 1, and put a 1 at the end
case head #:: tail if (head > 1) =>
Some((head - 1) #:: tail #::: Stream(1))

//otherwise, it's not possible.
case _ => None
}

def rec(sum: Sum): Stream[Sum] = {
schmear(sum) match {
case Some(schmeared) => sum #:: rec(schmeared)
case None => Stream(sum)
}
}

//initiate the recursive algorithm with the sum of the identity
rec(Stream(i))
}


Using this:


println(makesums(5).map(_.toList).toList)


List(List(5), List(4, 1), List(3, 2), List(2, 2, 1), L

Apart from the five cases you have to distinguish, there is a more
severe problem with the code as it is: It misses some sums. In your
example of sums adding up to 5 it is the sum 3+1+1 that is missed. The
higher the number, the more sums will be missed.

The reason is that your algorithm greedily "schmears" down one from
the first number whenever possible. However, this should only happen
if the rest of the sum can not be schmeared anymore. So in your
example you have 3+2 and you try to reduce the 3 instead of splitting
up the 2 first.

If you fix that, an important consequence is that it is not sufficient
to modify the sum by schmearing alone, but you have to "reset" parts
of it it occasionally. If you go from 3+2 to 3+1+1, you cannot reach
2+2+1 anymore by schmearing.

A better strategy is trying to schmear the tail first and only if this
is not possible anymore, reduce the first number and reset the tail to
the most compact form not violating your invariants. This is what
uniformSum does in the following listing. Lets say your total is 10
and you reduce the first number to 3, then it sets the sum to 3+3+3+1.

type Sum = List[Int]

def sums(n: Int): Stream[Sum] = schmearStream(List(n))

def schmearStream(sum: Sum): Stream[Sum] =
  sum #:: (schmear(sum) map (schmearStream(_)) getOrElse Empty)

def schmear(nums: Sum): Option[Sum] =
  if (nums.isEmpty || nums.head == 1) None
  else schmear(nums.tail) match {
    case Some(schmearedTail) => Some(nums.head :: schmearedTail)
    case None => Some(uniformSum(nums.sum, nums.head - 1))
  }

def uniformSum(sum: Int, num: Int): Sum = {
  val rest = sum % num
  List.fill(sum / num)(num) ::: (if (rest == 0) Nil else List(rest))
}

You also see that it is sufficient to distinguish fewer cases because
you don't need a lookahead of 2. As long we don't have an
unschmearable sum (empty or starts with 1), we only care if we can
schmear the tail or not.

I tried to write it in a very compact form. If you think a function
should be more verbose for the sake of better readability, please let
me know.

StackExchange Code Review Q#115687, answer score: 3