Re: code question and challenge (Partition generator)

[Kevin Squire]

Hello, scala-user,

In the end, I came up with the attached version of my partition
generator.  Manohar's version was quite elegant, worked well and was
very instructive.  EastSun showed that it was possible to create an
iterator to generate the sequence.  I used this idea, but came up with
a recursive sequence generator.

It's a more straightforward use of streams than Manohars, if not quite
as elegant, but I got the chance to more about Streams and pattern
matching, and I'm happy with it.  Any further comments welcome.

Thanks all who offered help!

Kevin


----

object Partition {

  // Gives a stream of the partitions of n
  def getParts(n: Int) = {
    def getPartStream(part: List[Int]): Stream[List[Int]] = part match {
      case Nil => Stream.empty
      case _ => Stream.cons(part, getPartStream(nextPart(n,part)))
    }

    if (n < 0)
      Stream.empty
    else if (n == 0)
      Stream(List(0))
    else
      getPartStream(List(n))
  }

  // Given n and a partition of n, generate the next partition
  def nextPart(n: Int, prevPart: List[Int]): List[Int] = prevPart match {
    case Nil          => Nil
    case 1 :: _       => Nil
    case x :: Nil     => List(x-1,1)
    case x :: 1 :: _  => x-1 :: genFirstPart(n-(x-1), x-1)
    case x :: xs      => x :: nextPart(n-x, xs)
  }

  // Given n and a maximum value, generate the first partition of n
  // using values max or smaller
  def genFirstPart(n: Int, max: Int): List[Int] = {
    if (n <= max)
      List(n)
    else
      max :: genFirstPart(n-max,max)
  }
}




On Sun, Nov 1, 2009 at 10:31 AM, Kevin Squire <kevin.squire@...> wrote:

> Hello, scala-user,
>
> I've written some code to find all of the partitions of a number (see
> http://en.wikipedia.org/wiki/Partition_(number_theory) ).
>
> scala> Partition.getParts(5) mkString "\n"
> res2: String =
> Partition(5)
> Partition(4, 1)
> Partition(3, 2)
> Partition(3, 1, 1)
> Partition(2, 2, 1)
> Partition(2, 1, 1, 1)
> Partition(1, 1, 1, 1, 1)
>
> The code is below.  I'm wondering about the following:
>
> 1) I'd like a function which only gives me a certain number of
> partitions.  E.g., I can do
>
> scala> Partition.getParts(5) take 4 mkString "\n"
> res4: String =
> Partition(5)
> Partition(4, 1)
> Partition(3, 2)
> Partition(3, 1, 1)
>
> But, this code generates all partitions first, and then gives me the
> first four.  How can I change the code to only produce the partitions
> I want?
>
> 2) I've produced a memoized version (getPartsMemo) for efficiency,
> using a mutable map.  Is there a better way to make the code more
> efficient (or improve the version I created)?
>
> In particular, for both of these questions, I want to generate the
> first 10 or 20 (or 50 or 100 or 1000) partitions of larger numbers
> (say 500 or 10000).
>
> Any other comments or suggestions about the code are welcome.
>
> Thanks!
>
> Kevin