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 &gt;= s + 1) =&gt;
      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 &gt; s =&gt;
      schmear((s + 1) #:: tail).map(nt =&gt; (head - 1) #:: nt)

    //otherwise, if there are at least two elements, just schmear the tail, 
    //and keep the orignal head
    case head #:: s #:: tail =&gt;
      schmear(s #:: tail).map(nt =&gt; 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 &gt; 1) =&gt;
      Some((head - 1) #:: tail  #::: Stream(1))

    //otherwise, it's not possible.
    case _ =&gt; None
  }

  def rec(sum: Sum): Stream[Sum] = {
    schmear(sum) match {
      case Some(schmeared) =&gt; sum #:: rec(schmeared)
      case None            =&gt; 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), List(2, 1, 1, 1), List(1, 1, 1, 1, 1))


Going through the algorithm:


Stream(5) takes case 4, yielding Stream(4, 1)
Stream(4, 1) takes case 1, yielding Stream(3, 2)
Stream(3, 2) takes case 2, starting with (3 - 1) = 2, and recurses with Stream(2 + 1) for the tail


Stream(3) takes case 4, yielding Stream(2, 1)

yielding Stream(2, 2, 1)
Stream(2, 2, 1) takes case 3, starting with 2, and recurses with Stream(2, 1)


Stream(2, 1) takes case 2, starting with (2 - 1) = 1, and recurses with Stream(2) for the tail
Stream(2) takes case 4, yielding Stream(1, 1)
yielding Stream(1, 1, 1)

yielding Stream(2, 1, 1, 1)
Stream(2, 1, 1, 1) takes case 2, taking 1 for the head, and recursing with Stream(2, 1, 1) for the tail


keep taking case 2 until you heave Stream(2)
Stream(2) takes case 4, yielding Stream(1, 1)

yielding Stream(1, 1, 1, 1, 1)


but if feels really complicated. In particular, having 5 different cases for the schmearing, which seems way more complicated than describing what you do.

What can I do to simplify this?
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) =&gt; Some(nums.head :: schmearedTail)
    case None =&gt; 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.