Distinct sums of integers

Question

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), 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?

Answer 1

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.

Answer 2

OK I think I understand the problem: given an integer n, you want to generate a list (or Stream) of all integer partitions of n. To facilitate uniqueness up to reordering, we impose the requirement that all lists are in weakly-decreasing order.

I'm not sure if you really need to make the type type Sum = Stream[Int]. It depends on how often you use that type throughout the rest of your code. Either way, you should change the name --- maybe call it Parition.

I think your code is quite readable, and I don't think with your algorithm there's a good way around having five cases. Five cases is not too much anyhow. However, you should make your cases a little clearer.

A clearer way to write your first case is

case head #:: s #:: tail if (head - 2 >= s)

and then your second case should be

case head #:: s #:: tail if head - 1 == s

which is more explicit.

Alternatively, here's my implementation. I went a different route than you that allowed my code to be a bit more linear (less cases). Neither is better or worse, just different. Here is my code:

object DistinctSums {
  private def allDistinctSumsHelper(n: Int, upperBound: Int): Stream[List[Int]] = {
    n match {
        case 0 => Stream(Nil)
        case 1 => Stream(List(1))
        case _ => (1 to upperBound)
                    .toStream
                    .map(x =>
                        allDistinctSumsHelper(n-x, x)
                        .map(xs => x::xs)
                    ).flatten
                    .toStream
    }
  }

  def allDistinctSums(n: Int) = allDistinctSumsHelper(n, n)

  def main(args: Array[String]): Unit = {
    println(allDistinctSums(6, 6) take 8 toList)
  }
}

I chose to make it a Stream of Lists, as the inner lists shouldn't be that large.

Answer 3

Types

Representing each Sum as a Stream[Int] doesn't make much sense. Each sum is of a manageable size, so a List[Int] would do just fine.

Based on What is the difference between view, stream and iterator?, I would say that an Iterator[Sum] would be more appropriate than a Stream[Sum]. The results aren't infinite, and you don't need them to be cached. If you do want a Stream, you can easily call toStream on the result.

Bug

Your solution fails to decompose 5 = 3 + 1 + 1, as evidenced by your sample output.

Algorithm

The solution is simpler if you output with List(n) last, because it is easier to detect that case than to detect List(1, 1, 1, …, 1).

You are better off manipulating lists at the head end, because #::: concatenation is bad for efficiency. The example at the end illustrates the improvement.

Here is a solution based on this Java code, with credits to @rolfl for the algorithm:

/** List of non-increasing positive integers */
type Sum = List[Int]

def sums(n: Int): Iterator[Sum] = {
  /** Prepends the head of the stack repeatedly until a total amount has
    * been added.  The leading element of the result is then increased
    * so that the total added is exactly the specified amount.
    */
  @tailrec
  def topUp(amount: Int, stack: List[Int]): List[Int] = {
    if (amount < stack.head)
      (stack.head + amount) :: stack.tail
    else
      topUp(amount - stack.head, stack.head :: stack)
  }

  /** Returns the next partition by popping the first element, increasing the
    * next element, and topping it up to the same total.  Returns None if
    * the input has only one element.
    */
  def advance(partition: Option[Sum]): Option[Sum] = {
    partition.get match {
      case List(n) => None
      case p       => Some(topUp(p.head - 1, p.tail.head + 1 :: p.tail.tail))
    }
  }

  Iterator.iterate(Some(List.fill(n)(1)): Option[Sum])(advance)
          .takeWhile(! _.isEmpty)
          .map(_.get)
}

---

Example run:

scala> sums(5).foreach(println)
List(1, 1, 1, 1, 1)
List(2, 1, 1, 1)
List(3, 1, 1)
List(2, 2, 1)
List(4, 1)
List(3, 2)
List(5)

Notice how this output order is more efficient than your original order. For example, going from List(1, 1, 1, 1, 1) to List(2, 1, 1, 1) involves just a pop-pop-push, whereas going from List(2, 1, 1, 1) to List(1, 1, 1, 1, 1) involves rewriting everything.