code question and challenge

[Kevin Squire]

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

------------

import scala.collection.mutable.Map

// Partition class

class Partition (val part: List[Int]) {
    def this(v: Int*) = this(v toList)
    def this(v: Int, subPart: List[Int]) = this(v :: subPart)

    override def toString = part.mkString("Partition(",", ",")")
}

object Partition {

  implicit def partWrapper(p: Partition): List[Int] = p.part

  val emptyPartList = List[Partition]()

  def ones(n: Int) = (for (x <- 1 to n) yield 1) toList

///////////////////////
// Find all partitions of n
///////////////////////

  def getParts(n:Int) : List[Partition] = {

    ///////////////////////
    // Find all partitions of n using natural numbers at most as large as k
    //
    // (inspired by, but different from
    //  http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
)
    ///////////////////////

    def getParts2(k: Int, n: Int): List[Partition] = {
      if (k == 1)  // Stopping condition:
        List(new Partition(ones(n)))
      else if (k == n) // Special case to produce Partition(n) as a partition
        List(new Partition(n)) ::: getParts2(k-1,n)
      else {
        // find all partitions which start with k
        val temp = getParts2(Math.min(k,n-k),n-k)
        val parts_k = temp map (p => new Partition(k,p))

        // find all partitions using numbers at most as large as k-1
        val parts_k_1 = getParts2(k-1,n)

        // put these lists together
        parts_k ::: parts_k_1
      }
    }

    if (n < 0)
      emptyPartList  // by def
    if (n == 0)
      List(new Partition(0))  // by def (and the code above doesn't handle this)
    else
      getParts2(n,n)

  }

  //////////////////////

  def getPartsMemo(n:Int) : List[Partition] = {

    var parts2map = Map[Tuple2[Int,Int], List[Partition]]()

    def getParts2(k: Int, n: Int): List[Partition] = {
      if (!parts2map.contains((k,n))) {
        if (k == 1)
          parts2map += ((k,n) -> List(new Partition(ones(n))))
        else if (k == n) {
          parts2map += ((k,n) -> (List(new Partition(n)) ::: getParts2(k-1,n)))
        }
        else {
          val temp = getParts2(Math.min(k,n-k),n-k)
          val parts_k = temp map (p => new Partition(k,p))
          val parts_k_1 = getParts2(k-1,n)
          parts2map += ((k,n) -> (parts_k ::: parts_k_1))
        }
      }
      parts2map((k,n))
    }

    if (n < 0)
      emptyPartList
    if (n == 0)
      List(new Partition(0))
    else
      getParts2(n,n)

  }
}

[Daniel Sobral]

If you just change from List to Stream, you already save some work, as streams are non-strict lists.

Use #::: instead of :::. I didn't see any :: in your code, by #:: is the Stream-equivalent for that.

Basically, the right side won't be computed unless required.

If you can change your code to be mostly recursive, and always use #:: instead of #:::, you'll get what you wanted.

On Sun, Nov 1, 2009 at 4:31 PM, 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

------------

import scala.collection.mutable.Map

// Partition class

class Partition (val part: List[Int]) {
    def this(v: Int*) = this(v toList)
    def this(v: Int, subPart: List[Int]) = this(v :: subPart)

    override def toString = part.mkString("Partition(",", ",")")
}

object Partition {

 implicit def partWrapper(p: Partition): List[Int] = p.part

 val emptyPartList = List[Partition]()

 def ones(n: Int) = (for (x <- 1 to n) yield 1) toList

///////////////////////
// Find all partitions of n
///////////////////////

 def getParts(n:Int) : List[Partition] = {

   ///////////////////////
   // Find all partitions of n using natural numbers at most as large as k
   //
   // (inspired by, but different from
   //  http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
)
   ///////////////////////

   def getParts2(k: Int, n: Int): List[Partition] = {
     if (k == 1)  // Stopping condition:
       List(new Partition(ones(n)))
     else if (k == n) // Special case to produce Partition(n) as a partition
       List(new Partition(n)) ::: getParts2(k-1,n)
     else {
       // find all partitions which start with k
       val temp = getParts2(Math.min(k,n-k),n-k)
       val parts_k = temp map (p => new Partition(k,p))

       // find all partitions using numbers at most as large as k-1
       val parts_k_1 = getParts2(k-1,n)

       // put these lists together
       parts_k ::: parts_k_1
     }
   }

   if (n < 0)
     emptyPartList  // by def
   if (n == 0)
     List(new Partition(0))  // by def (and the code above doesn't handle this)
   else
     getParts2(n,n)

 }

 //////////////////////

 def getPartsMemo(n:Int) : List[Partition] = {

   var parts2map = Map[Tuple2[Int,Int], List[Partition]]()

   def getParts2(k: Int, n: Int): List[Partition] = {
     if (!parts2map.contains((k,n))) {
       if (k == 1)
         parts2map += ((k,n) -> List(new Partition(ones(n))))
       else if (k == n) {
         parts2map += ((k,n) -> (List(new Partition(n)) ::: getParts2(k-1,n)))
       }
       else {
         val temp = getParts2(Math.min(k,n-k),n-k)
         val parts_k = temp map (p => new Partition(k,p))
         val parts_k_1 = getParts2(k-1,n)
         parts2map += ((k,n) -> (parts_k ::: parts_k_1))
       }
     }
     parts2map((k,n))
   }

   if (n < 0)
     emptyPartList
   if (n == 0)
     List(new Partition(0))
   else
     getParts2(n,n)

 }
}

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

[Manohar Jonnalagedda]

Hi,

I agree with Daniel about the streams. Using an explicit HashMap is also a good idea in my opinion. Moreover, I think the code can be written more elegantly as follows (addons on top of mine are also welcome) :

object Partition{
 
  def main(args : Array[String]) = {
    println("Hello World")
    miniPartitions(5,0).print
    miniPartitions(2,0).print
    partition(3).print
    partition(8).print
  }
 
  val memoMap = new HashMap[Int, Stream[List[Int]]]
 
  def memorablePartition(aNumber : Int) = memoMap.get(aNumber) match {
    case None =>
      val temp = partition(aNumber); memoMap += aNumber -> temp; temp
    case Some(x) => x
  }
 
  def partition(aNumber : Int) : Stream[List[Int]] = aNumber match{
    case 0 => Stream.cons(Nil, Stream.empty)
    case _ =>
      val temp = miniPartitions(aNumber, 0)
      temp.flatMap{case (l,r) => 
        val newTemp : Stream[List[Int]] = memorablePartition(r).filter(xs => xs.forall(x => x <= l))
        newTemp.map(xs => l::xs)
      }
  }
 
  def miniPartitions(a : Int, b: Int) : Stream[Pair[Int,Int]] =
    if(a == 0) Stream.empty
    else Stream.cons((a,b), miniPartitions(a-1, b+1))

}


Cheers,
Manohar

On Sun, Nov 1, 2009 at 12:19 PM, Daniel Sobral <dcsobral@...> wrote:

If you just change from List to Stream, you already save some work, as streams are non-strict lists.

Use #::: instead of :::. I didn't see any :: in your code, by #:: is the Stream-equivalent for that.

Basically, the right side won't be computed unless required.

If you can change your code to be mostly recursive, and always use #:: instead of #:::, you'll get what you wanted.

On Sun, Nov 1, 2009 at 4:31 PM, 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

------------

import scala.collection.mutable.Map

// Partition class

class Partition (val part: List[Int]) {
    def this(v: Int*) = this(v toList)
    def this(v: Int, subPart: List[Int]) = this(v :: subPart)

    override def toString = part.mkString("Partition(",", ",")")
}

object Partition {

 implicit def partWrapper(p: Partition): List[Int] = p.part

 val emptyPartList = List[Partition]()

 def ones(n: Int) = (for (x <- 1 to n) yield 1) toList

///////////////////////
// Find all partitions of n
///////////////////////

 def getParts(n:Int) : List[Partition] = {

   ///////////////////////
   // Find all partitions of n using natural numbers at most as large as k
   //
   // (inspired by, but different from
   //  http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
)
   ///////////////////////

   def getParts2(k: Int, n: Int): List[Partition] = {
     if (k == 1)  // Stopping condition:
       List(new Partition(ones(n)))
     else if (k == n) // Special case to produce Partition(n) as a partition
       List(new Partition(n)) ::: getParts2(k-1,n)
     else {
       // find all partitions which start with k
       val temp = getParts2(Math.min(k,n-k),n-k)
       val parts_k = temp map (p => new Partition(k,p))

       // find all partitions using numbers at most as large as k-1
       val parts_k_1 = getParts2(k-1,n)

       // put these lists together
       parts_k ::: parts_k_1
     }
   }

   if (n < 0)
     emptyPartList  // by def
   if (n == 0)
     List(new Partition(0))  // by def (and the code above doesn't handle this)
   else
     getParts2(n,n)

 }

 //////////////////////

 def getPartsMemo(n:Int) : List[Partition] = {

   var parts2map = Map[Tuple2[Int,Int], List[Partition]]()

   def getParts2(k: Int, n: Int): List[Partition] = {
     if (!parts2map.contains((k,n))) {
       if (k == 1)
         parts2map += ((k,n) -> List(new Partition(ones(n))))
       else if (k == n) {
         parts2map += ((k,n) -> (List(new Partition(n)) ::: getParts2(k-1,n)))
       }
       else {
         val temp = getParts2(Math.min(k,n-k),n-k)
         val parts_k = temp map (p => new Partition(k,p))
         val parts_k_1 = getParts2(k-1,n)
         parts2map += ((k,n) -> (parts_k ::: parts_k_1))
       }
     }
     parts2map((k,n))
   }

   if (n < 0)
     emptyPartList
   if (n == 0)
     List(new Partition(0))
   else
     getParts2(n,n)

 }
}

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

[Eastsun]

How about this:

C:\Documents and Settings\Admin>scala
Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM) Client VM, Java 1.6.0_16).
Type in expressions to have them evaluated.
Type :help for more information.

scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
     |     val nums = new Array[Int](n+1)
     |     nums(0) = n
     |     var end = 1
     |
     |     override def hasNext = end <= n
     |
     |     override def next: List[Int] = {
     |         if(!hasNext) Iterator.empty.next
     |         val res = nums.view.slice(0,end).toList
     |         var (fst,sec) = (end-1,end)
     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
     |         if(fst >= 0) sec = fst + 1
     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
     |         if(sec == end) end += 1
     |         if(end <= n) {
     |             nums(sec) += 1
     |             nums(fst) -= 1
     |         }
     |         res
     |     }
     | }
defined class PartsItr

scala> val itr = new PartsItr(100000)
itr: PartsItr = non-empty iterator

scala> val first100 = itr take 100
first100: Iterator[List[Int]] = non-empty iterator

scala> first100 foreach println
List(100000)
List(99999, 1)
List(99998, 2)
List(99998, 1, 1)
List(99997, 2, 1)
List(99996, 3, 1)
List(99996, 2, 2)
List(99996, 2, 1, 1)
List(99995, 3, 1, 1)
List(99995, 2, 2, 1)
List(99994, 3, 2, 1)
List(99993, 4, 2, 1)
List(99993, 3, 3, 1)
List(99993, 3, 2, 2)
List(99993, 3, 2, 1, 1)
List(99992, 4, 2, 1, 1)
List(99992, 3, 3, 1, 1)
List(99992, 3, 2, 2, 1)
List(99991, 4, 2, 2, 1)
List(99991, 3, 3, 2, 1)
List(99990, 4, 3, 2, 1)
List(99989, 5, 3, 2, 1)
List(99989, 4, 4, 2, 1)
List(99989, 4, 3, 3, 1)
List(99989, 4, 3, 2, 2)
List(99989, 4, 3, 2, 1, 1)

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

------------

import scala.collection.mutable.Map

// Partition class

class Partition (val part: List[Int]) {
    def this(v: Int*) = this(v toList)
    def this(v: Int, subPart: List[Int]) = this(v :: subPart)

    override def toString = part.mkString("Partition(",", ",")")
}

object Partition {

  implicit def partWrapper(p: Partition): List[Int] = p.part

  val emptyPartList = List[Partition]()

  def ones(n: Int) = (for (x <- 1 to n) yield 1) toList

///////////////////////
// Find all partitions of n
///////////////////////

  def getParts(n:Int) : List[Partition] = {

    ///////////////////////
    // Find all partitions of n using natural numbers at most as large as k
    //
    // (inspired by, but different from
    //  http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
)
    ///////////////////////

    def getParts2(k: Int, n: Int): List[Partition] = {
      if (k == 1)  // Stopping condition:
        List(new Partition(ones(n)))
      else if (k == n) // Special case to produce Partition(n) as a partition
        List(new Partition(n)) ::: getParts2(k-1,n)
      else {
        // find all partitions which start with k
        val temp = getParts2(Math.min(k,n-k),n-k)
        val parts_k = temp map (p => new Partition(k,p))

        // find all partitions using numbers at most as large as k-1
        val parts_k_1 = getParts2(k-1,n)

        // put these lists together
        parts_k ::: parts_k_1
      }
    }

    if (n < 0)
      emptyPartList  // by def
    if (n == 0)
      List(new Partition(0))  // by def (and the code above doesn't handle this)
    else
      getParts2(n,n)

  }

  //////////////////////

  def getPartsMemo(n:Int) : List[Partition] = {

    var parts2map = Map[Tuple2[Int,Int], List[Partition]]()

    def getParts2(k: Int, n: Int): List[Partition] = {
      if (!parts2map.contains((k,n))) {
        if (k == 1)
          parts2map += ((k,n) -> List(new Partition(ones(n))))
        else if (k == n) {
          parts2map += ((k,n) -> (List(new Partition(n)) ::: getParts2(k-1,n)))
        }
        else {
          val temp = getParts2(Math.min(k,n-k),n-k)
          val parts_k = temp map (p => new Partition(k,p))
          val parts_k_1 = getParts2(k-1,n)
          parts2map += ((k,n) -> (parts_k ::: parts_k_1))
        }
      }
      parts2map((k,n))
    }

    if (n < 0)
      emptyPartList
    if (n == 0)
      List(new Partition(0))
    else
      getParts2(n,n)

  }
}

[Kevin Squire]

Daniel and Manohar,

Thank you!  I'm still have a lot of Java-isms on the mind, and I'm not
at all used to Streams and matching yet--thanks for the ideas and
example.

Manohar, I liked how you eliminated the need for my inner function by
filtering out "smaller" streams whose numbers were larger than the
first number.  Just to clarify, when newTemp.map(xs => l::xs) is
executed, can we assume that the stream elements are not yet
evalutated?

Kevin


On Sun, Nov 1, 2009 at 2:46 PM, Manohar Jonnalagedda
<manojo10386@...> wrote:

> Hi,
>
> I agree with Daniel about the streams. Using an explicit HashMap is also a
> good idea in my opinion. Moreover, I think the code can be written more
> elegantly as follows (addons on top of mine are also welcome) :
>
> object Partition{
>
>   def main(args : Array[String]) = {
>     println("Hello World")
>     miniPartitions(5,0).print
>     miniPartitions(2,0).print
>     partition(3).print
>     partition(8).print
>   }
>
>   val memoMap = new HashMap[Int, Stream[List[Int]]]
>
>   def memorablePartition(aNumber : Int) = memoMap.get(aNumber) match {
>     case None =>
>       val temp = partition(aNumber); memoMap += aNumber -> temp; temp
>     case Some(x) => x
>   }
>
>   def partition(aNumber : Int) : Stream[List[Int]] = aNumber match{
>     case 0 => Stream.cons(Nil, Stream.empty)
>     case _ =>
>       val temp = miniPartitions(aNumber, 0)
>       temp.flatMap{case (l,r) =>
>         val newTemp : Stream[List[Int]] = memorablePartition(r).filter(xs =>
> xs.forall(x => x <= l))
>         newTemp.map(xs => l::xs)
>       }
>   }
>
>   def miniPartitions(a : Int, b: Int) : Stream[Pair[Int,Int]] =
>     if(a == 0) Stream.empty
>     else Stream.cons((a,b), miniPartitions(a-1, b+1))
>
> }
>
>
> Cheers,
> Manohar

[Kevin Squire]

Eastsun,

That's clever.  One problem, though, is that it does not currently
preserve the order of the generated partitions, which I need.

(Technically, the list of partitions form a dominance order (partial
order), which I haven't quite determined how to deal with conceptually
in the application I'm targeting.)

Kevin

On Sun, Nov 1, 2009 at 5:42 PM, Eastsun <flushtime@...> wrote:

>
> How about this::working:
>
> C:\Documents and Settings\Admin>scala
> Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM)
> Client VM, Java 1.6.0_16).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>     |     val nums = new Array[Int](n+1)
>     |     nums(0) = n
>     |     var end = 1
>     |
>     |     override def hasNext = end <= n
>     |
>     |     override def next: List[Int] = {
>     |         if(!hasNext) Iterator.empty.next
>     |         val res = nums.view.slice(0,end).toList
>     |         var (fst,sec) = (end-1,end)
>     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
>     |         if(fst >= 0) sec = fst + 1
>     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
>     |         if(sec == end) end += 1
>     |         if(end <= n) {
>     |             nums(sec) += 1
>     |             nums(fst) -= 1
>     |         }
>     |         res
>     |     }
>     | }
> defined class PartsItr
>
> scala> val itr = new PartsItr(100000)
> itr: PartsItr = non-empty iterator
>
> scala> val first100 = itr take 100
> first100: Iterator[List[Int]] = non-empty iterator
>
> scala> first100 foreach println
> List(100000)
> List(99999, 1)
> List(99998, 2)
> List(99998, 1, 1)
> List(99997, 2, 1)
> List(99996, 3, 1)
> List(99996, 2, 2)
> List(99996, 2, 1, 1)
> List(99995, 3, 1, 1)
> List(99995, 2, 2, 1)
> List(99994, 3, 2, 1)
> List(99993, 4, 2, 1)
> List(99993, 3, 3, 1)
> List(99993, 3, 2, 2)
> List(99993, 3, 2, 1, 1)
> List(99992, 4, 2, 1, 1)
> List(99992, 3, 3, 1, 1)
> List(99992, 3, 2, 2, 1)
> List(99991, 4, 2, 2, 1)
> List(99991, 3, 3, 2, 1)
> List(99990, 4, 3, 2, 1)
> List(99989, 5, 3, 2, 1)
> List(99989, 4, 4, 2, 1)
> List(99989, 4, 3, 3, 1)
> List(99989, 4, 3, 2, 2)
> List(99989, 4, 3, 2, 1, 1)
>
>
> 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
>>
>> ------------
>>
>> import scala.collection.mutable.Map
>>
>> // Partition class
>>
>> class Partition (val part: List[Int]) {
>>     def this(v: Int*) = this(v toList)
>>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>>
>>     override def toString = part.mkString("Partition(",", ",")")
>> }
>>
>> object Partition {
>>
>>   implicit def partWrapper(p: Partition): List[Int] = p.part
>>
>>   val emptyPartList = List[Partition]()
>>
>>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>>
>> ///////////////////////
>> // Find all partitions of n
>> ///////////////////////
>>
>>   def getParts(n:Int) : List[Partition] = {
>>
>>     ///////////////////////
>>     // Find all partitions of n using natural numbers at most as large as
>> k
>>     //
>>     // (inspired by, but different from
>>     //
>> http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
>> )
>>     ///////////////////////
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (k == 1)  // Stopping condition:
>>         List(new Partition(ones(n)))
>>       else if (k == n) // Special case to produce Partition(n) as a
>> partition
>>         List(new Partition(n)) ::: getParts2(k-1,n)
>>       else {
>>         // find all partitions which start with k
>>         val temp = getParts2(Math.min(k,n-k),n-k)
>>         val parts_k = temp map (p => new Partition(k,p))
>>
>>         // find all partitions using numbers at most as large as k-1
>>         val parts_k_1 = getParts2(k-1,n)
>>
>>         // put these lists together
>>         parts_k ::: parts_k_1
>>       }
>>     }
>>
>>     if (n < 0)
>>       emptyPartList  // by def
>>     if (n == 0)
>>       List(new Partition(0))  // by def (and the code above doesn't handle
>> this)
>>     else
>>       getParts2(n,n)
>>
>>   }
>>
>>   //////////////////////
>>
>>   def getPartsMemo(n:Int) : List[Partition] = {
>>
>>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (!parts2map.contains((k,n))) {
>>         if (k == 1)
>>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>>         else if (k == n) {
>>           parts2map += ((k,n) -> (List(new Partition(n)) :::
>> getParts2(k-1,n)))
>>         }
>>         else {
>>           val temp = getParts2(Math.min(k,n-k),n-k)
>>           val parts_k = temp map (p => new Partition(k,p))
>>           val parts_k_1 = getParts2(k-1,n)
>>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>>         }
>>       }
>>       parts2map((k,n))
>>     }
>>
>>     if (n < 0)
>>       emptyPartList
>>     if (n == 0)
>>       List(new Partition(0))
>>     else
>>       getParts2(n,n)
>>
>>   }
>> }
>>
>>
>
>
> -----
> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
> http://eastsun.javaeye.com/category/34059 Click here
> --
> View this message in context: http://old.nabble.com/code-question-and-challenge-tp26153489p26155430.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>

[Manohar Jonnalagedda]

Kevin,

Just to clarify, when newTemp.map(xs => l::xs) is
executed, can we assume that the stream elements are not yet
evalutated?

I think it is indeed safe to assume so. If you want to make sure, just run it through a debugger or add some print lines at the key areas.

Manohar

On Sun, Nov 1, 2009 at 2:46 PM, Manohar Jonnalagedda
<manojo10386@...> wrote:
> Hi,
>
> I agree with Daniel about the streams. Using an explicit HashMap is also a
> good idea in my opinion. Moreover, I think the code can be written more
> elegantly as follows (addons on top of mine are also welcome) :
>
> object Partition{
>
>   def main(args : Array[String]) = {
>     println("Hello World")
>     miniPartitions(5,0).print
>     miniPartitions(2,0).print
>     partition(3).print
>     partition(8).print
>   }
>
>   val memoMap = new HashMap[Int, Stream[List[Int]]]
>
>   def memorablePartition(aNumber : Int) = memoMap.get(aNumber) match {
>     case None =>
>       val temp = partition(aNumber); memoMap += aNumber -> temp; temp
>     case Some(x) => x
>   }
>
>   def partition(aNumber : Int) : Stream[List[Int]] = aNumber match{
>     case 0 => Stream.cons(Nil, Stream.empty)
>     case _ =>
>       val temp = miniPartitions(aNumber, 0)
>       temp.flatMap{case (l,r) =>
>         val newTemp : Stream[List[Int]] = memorablePartition(r).filter(xs =>
> xs.forall(x => x <= l))
>         newTemp.map(xs => l::xs)
>       }
>   }
>
>   def miniPartitions(a : Int, b: Int) : Stream[Pair[Int,Int]] =
>     if(a == 0) Stream.empty
>     else Stream.cons((a,b), miniPartitions(a-1, b+1))
>
> }
>
>
> Cheers,
> Manohar

[Eastsun]

So what order do you want? Is not my code generate the same order as your?
My English is not very good, I'm not quite clear about your mean.

scala> new PartsItr(5) foreach println
List(5)
List(4, 1)
List(3, 2)
List(3, 1, 1)
List(2, 2, 1)
List(2, 1, 1, 1)
List(1, 1, 1, 1, 1)

Kevin Squire wrote:

Eastsun,

That's clever.  One problem, though, is that it does not currently
preserve the order of the generated partitions, which I need.

(Technically, the list of partitions form a dominance order (partial
order), which I haven't quite determined how to deal with conceptually
in the application I'm targeting.)

Kevin

On Sun, Nov 1, 2009 at 5:42 PM, Eastsun <[e-mail]> wrote:
>
> How about this::working:
>
> C:\Documents and Settings\Admin>scala
> Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM)
> Client VM, Java 1.6.0_16).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>     |     val nums = new Array[Int](n+1)
>     |     nums(0) = n
>     |     var end = 1
>     |
>     |     override def hasNext = end <= n
>     |
>     |     override def next: List[Int] = {
>     |         if(!hasNext) Iterator.empty.next
>     |         val res = nums.view.slice(0,end).toList
>     |         var (fst,sec) = (end-1,end)
>     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
>     |         if(fst >= 0) sec = fst + 1
>     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
>     |         if(sec == end) end += 1
>     |         if(end <= n) {
>     |             nums(sec) += 1
>     |             nums(fst) -= 1
>     |         }
>     |         res
>     |     }
>     | }
> defined class PartsItr
>
> scala> val itr = new PartsItr(100000)
> itr: PartsItr = non-empty iterator
>
> scala> val first100 = itr take 100
> first100: Iterator[List[Int]] = non-empty iterator
>
> scala> first100 foreach println
> List(100000)
> List(99999, 1)
> List(99998, 2)
> List(99998, 1, 1)
> List(99997, 2, 1)
> List(99996, 3, 1)
> List(99996, 2, 2)
> List(99996, 2, 1, 1)
> List(99995, 3, 1, 1)
> List(99995, 2, 2, 1)
> List(99994, 3, 2, 1)
> List(99993, 4, 2, 1)
> List(99993, 3, 3, 1)
> List(99993, 3, 2, 2)
> List(99993, 3, 2, 1, 1)
> List(99992, 4, 2, 1, 1)
> List(99992, 3, 3, 1, 1)
> List(99992, 3, 2, 2, 1)
> List(99991, 4, 2, 2, 1)
> List(99991, 3, 3, 2, 1)
> List(99990, 4, 3, 2, 1)
> List(99989, 5, 3, 2, 1)
> List(99989, 4, 4, 2, 1)
> List(99989, 4, 3, 3, 1)
> List(99989, 4, 3, 2, 2)
> List(99989, 4, 3, 2, 1, 1)
>
>
> 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
>>
>> ------------
>>
>> import scala.collection.mutable.Map
>>
>> // Partition class
>>
>> class Partition (val part: List[Int]) {
>>     def this(v: Int*) = this(v toList)
>>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>>
>>     override def toString = part.mkString("Partition(",", ",")")
>> }
>>
>> object Partition {
>>
>>   implicit def partWrapper(p: Partition): List[Int] = p.part
>>
>>   val emptyPartList = List[Partition]()
>>
>>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>>
>> ///////////////////////
>> // Find all partitions of n
>> ///////////////////////
>>
>>   def getParts(n:Int) : List[Partition] = {
>>
>>     ///////////////////////
>>     // Find all partitions of n using natural numbers at most as large as
>> k
>>     //
>>     // (inspired by, but different from
>>     //
>> http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
>> )
>>     ///////////////////////
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (k == 1)  // Stopping condition:
>>         List(new Partition(ones(n)))
>>       else if (k == n) // Special case to produce Partition(n) as a
>> partition
>>         List(new Partition(n)) ::: getParts2(k-1,n)
>>       else {
>>         // find all partitions which start with k
>>         val temp = getParts2(Math.min(k,n-k),n-k)
>>         val parts_k = temp map (p => new Partition(k,p))
>>
>>         // find all partitions using numbers at most as large as k-1
>>         val parts_k_1 = getParts2(k-1,n)
>>
>>         // put these lists together
>>         parts_k ::: parts_k_1
>>       }
>>     }
>>
>>     if (n < 0)
>>       emptyPartList  // by def
>>     if (n == 0)
>>       List(new Partition(0))  // by def (and the code above doesn't handle
>> this)
>>     else
>>       getParts2(n,n)
>>
>>   }
>>
>>   //////////////////////
>>
>>   def getPartsMemo(n:Int) : List[Partition] = {
>>
>>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (!parts2map.contains((k,n))) {
>>         if (k == 1)
>>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>>         else if (k == n) {
>>           parts2map += ((k,n) -> (List(new Partition(n)) :::
>> getParts2(k-1,n)))
>>         }
>>         else {
>>           val temp = getParts2(Math.min(k,n-k),n-k)
>>           val parts_k = temp map (p => new Partition(k,p))
>>           val parts_k_1 = getParts2(k-1,n)
>>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>>         }
>>       }
>>       parts2map((k,n))
>>     }
>>
>>     if (n < 0)
>>       emptyPartList
>>     if (n == 0)
>>       List(new Partition(0))
>>     else
>>       getParts2(n,n)
>>
>>   }
>> }
>>
>>
>
>
> -----
> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
> http://eastsun.javaeye.com/category/34059 Click here
> --
> View this message in context: http://old.nabble.com/code-question-and-challenge-tp26153489p26155430.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>

[Eastsun]

Sorry , I find that there is some bug in my code. I'll try to fix it

Kevin Squire wrote:

Eastsun,

That's clever.  One problem, though, is that it does not currently
preserve the order of the generated partitions, which I need.

(Technically, the list of partitions form a dominance order (partial
order), which I haven't quite determined how to deal with conceptually
in the application I'm targeting.)

Kevin

On Sun, Nov 1, 2009 at 5:42 PM, Eastsun <[e-mail]> wrote:
>
> How about this::working:
>
> C:\Documents and Settings\Admin>scala
> Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM)
> Client VM, Java 1.6.0_16).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>     |     val nums = new Array[Int](n+1)
>     |     nums(0) = n
>     |     var end = 1
>     |
>     |     override def hasNext = end <= n
>     |
>     |     override def next: List[Int] = {
>     |         if(!hasNext) Iterator.empty.next
>     |         val res = nums.view.slice(0,end).toList
>     |         var (fst,sec) = (end-1,end)
>     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
>     |         if(fst >= 0) sec = fst + 1
>     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
>     |         if(sec == end) end += 1
>     |         if(end <= n) {
>     |             nums(sec) += 1
>     |             nums(fst) -= 1
>     |         }
>     |         res
>     |     }
>     | }
> defined class PartsItr
>
> scala> val itr = new PartsItr(100000)
> itr: PartsItr = non-empty iterator
>
> scala> val first100 = itr take 100
> first100: Iterator[List[Int]] = non-empty iterator
>
> scala> first100 foreach println
> List(100000)
> List(99999, 1)
> List(99998, 2)
> List(99998, 1, 1)
> List(99997, 2, 1)
> List(99996, 3, 1)
> List(99996, 2, 2)
> List(99996, 2, 1, 1)
> List(99995, 3, 1, 1)
> List(99995, 2, 2, 1)
> List(99994, 3, 2, 1)
> List(99993, 4, 2, 1)
> List(99993, 3, 3, 1)
> List(99993, 3, 2, 2)
> List(99993, 3, 2, 1, 1)
> List(99992, 4, 2, 1, 1)
> List(99992, 3, 3, 1, 1)
> List(99992, 3, 2, 2, 1)
> List(99991, 4, 2, 2, 1)
> List(99991, 3, 3, 2, 1)
> List(99990, 4, 3, 2, 1)
> List(99989, 5, 3, 2, 1)
> List(99989, 4, 4, 2, 1)
> List(99989, 4, 3, 3, 1)
> List(99989, 4, 3, 2, 2)
> List(99989, 4, 3, 2, 1, 1)
>
>
> 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
>>
>> ------------
>>
>> import scala.collection.mutable.Map
>>
>> // Partition class
>>
>> class Partition (val part: List[Int]) {
>>     def this(v: Int*) = this(v toList)
>>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>>
>>     override def toString = part.mkString("Partition(",", ",")")
>> }
>>
>> object Partition {
>>
>>   implicit def partWrapper(p: Partition): List[Int] = p.part
>>
>>   val emptyPartList = List[Partition]()
>>
>>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>>
>> ///////////////////////
>> // Find all partitions of n
>> ///////////////////////
>>
>>   def getParts(n:Int) : List[Partition] = {
>>
>>     ///////////////////////
>>     // Find all partitions of n using natural numbers at most as large as
>> k
>>     //
>>     // (inspired by, but different from
>>     //
>> http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
>> )
>>     ///////////////////////
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (k == 1)  // Stopping condition:
>>         List(new Partition(ones(n)))
>>       else if (k == n) // Special case to produce Partition(n) as a
>> partition
>>         List(new Partition(n)) ::: getParts2(k-1,n)
>>       else {
>>         // find all partitions which start with k
>>         val temp = getParts2(Math.min(k,n-k),n-k)
>>         val parts_k = temp map (p => new Partition(k,p))
>>
>>         // find all partitions using numbers at most as large as k-1
>>         val parts_k_1 = getParts2(k-1,n)
>>
>>         // put these lists together
>>         parts_k ::: parts_k_1
>>       }
>>     }
>>
>>     if (n < 0)
>>       emptyPartList  // by def
>>     if (n == 0)
>>       List(new Partition(0))  // by def (and the code above doesn't handle
>> this)
>>     else
>>       getParts2(n,n)
>>
>>   }
>>
>>   //////////////////////
>>
>>   def getPartsMemo(n:Int) : List[Partition] = {
>>
>>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (!parts2map.contains((k,n))) {
>>         if (k == 1)
>>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>>         else if (k == n) {
>>           parts2map += ((k,n) -> (List(new Partition(n)) :::
>> getParts2(k-1,n)))
>>         }
>>         else {
>>           val temp = getParts2(Math.min(k,n-k),n-k)
>>           val parts_k = temp map (p => new Partition(k,p))
>>           val parts_k_1 = getParts2(k-1,n)
>>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>>         }
>>       }
>>       parts2map((k,n))
>>     }
>>
>>     if (n < 0)
>>       emptyPartList
>>     if (n == 0)
>>       List(new Partition(0))
>>     else
>>       getParts2(n,n)
>>
>>   }
>> }
>>
>>
>
>
> -----
> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
> http://eastsun.javaeye.com/category/34059 Click here
> --
> View this message in context: http://old.nabble.com/code-question-and-challenge-tp26153489p26155430.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>

[Eastsun]

A new version:

scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
     |     val nums = new Array[Int](n+1)
     |     nums(0) = n
     |     var end = 1
     |
     |     override def hasNext = end <= n
     |
     |     override def next: List[Int] = {
     |         if(!hasNext) Iterator.empty.next
     |         val res = nums.slice(0,end).toList
     |         var idx = nums.lastIndexWhere{ _ > 1 }
     |         if(idx == -1){
     |             end = n + 1
     |             return res
     |         }
     |         nums(idx) -= 1
     |         var sum = nums.slice(idx+1,end).foldLeft(1){ _+_ }
     |         val num = nums(idx)
     |         do {
     |             idx += 1
     |             nums(idx) = num min sum
     |             sum -= num
     |         }while(sum > 0)
     |         end = idx + 1
     |         res
     |     }
     | }
defined class PartsItr

scala> new PartsItr(8) foreach println
List(8)
List(7, 1)
List(6, 2)
List(6, 1, 1)
List(5, 3)
List(5, 2, 1)
List(5, 1, 1, 1)
List(4, 4)
List(4, 3, 1)
List(4, 2, 2)
List(4, 2, 1, 1)
List(4, 1, 1, 1, 1)
List(3, 3, 2)
List(3, 3, 1, 1)
List(3, 2, 2, 1)
List(3, 2, 1, 1, 1)
List(3, 1, 1, 1, 1, 1)
List(2, 2, 2, 2)
List(2, 2, 2, 1, 1)
List(2, 2, 1, 1, 1, 1)
List(2, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1)

Kevin Squire wrote:

Eastsun,

That's clever.  One problem, though, is that it does not currently
preserve the order of the generated partitions, which I need.

(Technically, the list of partitions form a dominance order (partial
order), which I haven't quite determined how to deal with conceptually
in the application I'm targeting.)

Kevin

On Sun, Nov 1, 2009 at 5:42 PM, Eastsun <[e-mail]> wrote:
>
> How about this::working:
>
> C:\Documents and Settings\Admin>scala
> Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM)
> Client VM, Java 1.6.0_16).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>     |     val nums = new Array[Int](n+1)
>     |     nums(0) = n
>     |     var end = 1
>     |
>     |     override def hasNext = end <= n
>     |
>     |     override def next: List[Int] = {
>     |         if(!hasNext) Iterator.empty.next
>     |         val res = nums.view.slice(0,end).toList
>     |         var (fst,sec) = (end-1,end)
>     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
>     |         if(fst >= 0) sec = fst + 1
>     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
>     |         if(sec == end) end += 1
>     |         if(end <= n) {
>     |             nums(sec) += 1
>     |             nums(fst) -= 1
>     |         }
>     |         res
>     |     }
>     | }
> defined class PartsItr
>
> scala> val itr = new PartsItr(100000)
> itr: PartsItr = non-empty iterator
>
> scala> val first100 = itr take 100
> first100: Iterator[List[Int]] = non-empty iterator
>
> scala> first100 foreach println
> List(100000)
> List(99999, 1)
> List(99998, 2)
> List(99998, 1, 1)
> List(99997, 2, 1)
> List(99996, 3, 1)
> List(99996, 2, 2)
> List(99996, 2, 1, 1)
> List(99995, 3, 1, 1)
> List(99995, 2, 2, 1)
> List(99994, 3, 2, 1)
> List(99993, 4, 2, 1)
> List(99993, 3, 3, 1)
> List(99993, 3, 2, 2)
> List(99993, 3, 2, 1, 1)
> List(99992, 4, 2, 1, 1)
> List(99992, 3, 3, 1, 1)
> List(99992, 3, 2, 2, 1)
> List(99991, 4, 2, 2, 1)
> List(99991, 3, 3, 2, 1)
> List(99990, 4, 3, 2, 1)
> List(99989, 5, 3, 2, 1)
> List(99989, 4, 4, 2, 1)
> List(99989, 4, 3, 3, 1)
> List(99989, 4, 3, 2, 2)
> List(99989, 4, 3, 2, 1, 1)
>
>
> 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
>>
>> ------------
>>
>> import scala.collection.mutable.Map
>>
>> // Partition class
>>
>> class Partition (val part: List[Int]) {
>>     def this(v: Int*) = this(v toList)
>>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>>
>>     override def toString = part.mkString("Partition(",", ",")")
>> }
>>
>> object Partition {
>>
>>   implicit def partWrapper(p: Partition): List[Int] = p.part
>>
>>   val emptyPartList = List[Partition]()
>>
>>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>>
>> ///////////////////////
>> // Find all partitions of n
>> ///////////////////////
>>
>>   def getParts(n:Int) : List[Partition] = {
>>
>>     ///////////////////////
>>     // Find all partitions of n using natural numbers at most as large as
>> k
>>     //
>>     // (inspired by, but different from
>>     //
>> http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
>> )
>>     ///////////////////////
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (k == 1)  // Stopping condition:
>>         List(new Partition(ones(n)))
>>       else if (k == n) // Special case to produce Partition(n) as a
>> partition
>>         List(new Partition(n)) ::: getParts2(k-1,n)
>>       else {
>>         // find all partitions which start with k
>>         val temp = getParts2(Math.min(k,n-k),n-k)
>>         val parts_k = temp map (p => new Partition(k,p))
>>
>>         // find all partitions using numbers at most as large as k-1
>>         val parts_k_1 = getParts2(k-1,n)
>>
>>         // put these lists together
>>         parts_k ::: parts_k_1
>>       }
>>     }
>>
>>     if (n < 0)
>>       emptyPartList  // by def
>>     if (n == 0)
>>       List(new Partition(0))  // by def (and the code above doesn't handle
>> this)
>>     else
>>       getParts2(n,n)
>>
>>   }
>>
>>   //////////////////////
>>
>>   def getPartsMemo(n:Int) : List[Partition] = {
>>
>>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (!parts2map.contains((k,n))) {
>>         if (k == 1)
>>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>>         else if (k == n) {
>>           parts2map += ((k,n) -> (List(new Partition(n)) :::
>> getParts2(k-1,n)))
>>         }
>>         else {
>>           val temp = getParts2(Math.min(k,n-k),n-k)
>>           val parts_k = temp map (p => new Partition(k,p))
>>           val parts_k_1 = getParts2(k-1,n)
>>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>>         }
>>       }
>>       parts2map((k,n))
>>     }
>>
>>     if (n < 0)
>>       emptyPartList
>>     if (n == 0)
>>       List(new Partition(0))
>>     else
>>       getParts2(n,n)
>>
>>   }
>> }
>>
>>
>
>
> -----
> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
> http://eastsun.javaeye.com/category/34059 Click here
> --
> View this message in context: http://old.nabble.com/code-question-and-challenge-tp26153489p26155430.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>

[Kevin Squire]

Eastsun,

Sorry, my initial example using the partitions of 5 was too short to
indicate the correct ordering.  What you have below is the correct
order.  Thanks!

Kevin

On Mon, Nov 2, 2009 at 10:08 AM, Eastsun <flushtime@...> wrote:

>
> A new version:
>
> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>     |     val nums = new Array[Int](n+1)
>     |     nums(0) = n
>     |     var end = 1
>     |
>     |     override def hasNext = end <= n
>     |
>     |     override def next: List[Int] = {
>     |         if(!hasNext) Iterator.empty.next
>     |         val res = nums.slice(0,end).toList
>     |         var idx = nums.lastIndexWhere{ _ > 1 }
>     |         if(idx == -1){
>     |             end = n + 1
>     |             return res
>     |         }
>     |         nums(idx) -= 1
>     |         var sum = nums.slice(idx+1,end).foldLeft(1){ _+_ }
>     |         val num = nums(idx)
>     |         do {
>     |             idx += 1
>     |             nums(idx) = num min sum
>     |             sum -= num
>     |         }while(sum > 0)
>     |         end = idx + 1
>     |         res
>     |     }
>     | }
> defined class PartsItr
>
> scala> new PartsItr(8) foreach println
> List(8)
> List(7, 1)
> List(6, 2)
> List(6, 1, 1)
> List(5, 3)
> List(5, 2, 1)
> List(5, 1, 1, 1)
> List(4, 4)
> List(4, 3, 1)
> List(4, 2, 2)
> List(4, 2, 1, 1)
> List(4, 1, 1, 1, 1)
> List(3, 3, 2)
> List(3, 3, 1, 1)
> List(3, 2, 2, 1)
> List(3, 2, 1, 1, 1)
> List(3, 1, 1, 1, 1, 1)
> List(2, 2, 2, 2)
> List(2, 2, 2, 1, 1)
> List(2, 2, 1, 1, 1, 1)
> List(2, 1, 1, 1, 1, 1, 1)
> List(1, 1, 1, 1, 1, 1, 1, 1)
>
>
>
>
> Kevin Squire wrote:
>>
>> Eastsun,
>>
>> That's clever.  One problem, though, is that it does not currently
>> preserve the order of the generated partitions, which I need.
>>
>> (Technically, the list of partitions form a dominance order (partial
>> order), which I haven't quite determined how to deal with conceptually
>> in the application I'm targeting.)
>>
>> Kevin
>>
>> On Sun, Nov 1, 2009 at 5:42 PM, Eastsun <flushtime@...> wrote:
>>>
>>> How about this::working:
>>>
>>> C:\Documents and Settings\Admin>scala
>>> Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM)
>>> Client VM, Java 1.6.0_16).
>>> Type in expressions to have them evaluated.
>>> Type :help for more information.
>>>
>>> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>>>     |     val nums = new Array[Int](n+1)
>>>     |     nums(0) = n
>>>     |     var end = 1
>>>     |
>>>     |     override def hasNext = end <= n
>>>     |
>>>     |     override def next: List[Int] = {
>>>     |         if(!hasNext) Iterator.empty.next
>>>     |         val res = nums.view.slice(0,end).toList
>>>     |         var (fst,sec) = (end-1,end)
>>>     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
>>>     |         if(fst >= 0) sec = fst + 1
>>>     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
>>>     |         if(sec == end) end += 1
>>>     |         if(end <= n) {
>>>     |             nums(sec) += 1
>>>     |             nums(fst) -= 1
>>>     |         }
>>>     |         res
>>>     |     }
>>>     | }
>>> defined class PartsItr
>>>
>>> scala> val itr = new PartsItr(100000)
>>> itr: PartsItr = non-empty iterator
>>>
>>> scala> val first100 = itr take 100
>>> first100: Iterator[List[Int]] = non-empty iterator
>>>
>>> scala> first100 foreach println
>>> List(100000)
>>> List(99999, 1)
>>> List(99998, 2)
>>> List(99998, 1, 1)
>>> List(99997, 2, 1)
>>> List(99996, 3, 1)
>>> List(99996, 2, 2)
>>> List(99996, 2, 1, 1)
>>> List(99995, 3, 1, 1)
>>> List(99995, 2, 2, 1)
>>> List(99994, 3, 2, 1)
>>> List(99993, 4, 2, 1)
>>> List(99993, 3, 3, 1)
>>> List(99993, 3, 2, 2)
>>> List(99993, 3, 2, 1, 1)
>>> List(99992, 4, 2, 1, 1)
>>> List(99992, 3, 3, 1, 1)
>>> List(99992, 3, 2, 2, 1)
>>> List(99991, 4, 2, 2, 1)
>>> List(99991, 3, 3, 2, 1)
>>> List(99990, 4, 3, 2, 1)
>>> List(99989, 5, 3, 2, 1)
>>> List(99989, 4, 4, 2, 1)
>>> List(99989, 4, 3, 3, 1)
>>> List(99989, 4, 3, 2, 2)
>>> List(99989, 4, 3, 2, 1, 1)
>>>
>>>
>>> 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
>>>>
>>>> ------------
>>>>
>>>> import scala.collection.mutable.Map
>>>>
>>>> // Partition class
>>>>
>>>> class Partition (val part: List[Int]) {
>>>>     def this(v: Int*) = this(v toList)
>>>>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>>>>
>>>>     override def toString = part.mkString("Partition(",", ",")")
>>>> }
>>>>
>>>> object Partition {
>>>>
>>>>   implicit def partWrapper(p: Partition): List[Int] = p.part
>>>>
>>>>   val emptyPartList = List[Partition]()
>>>>
>>>>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>>>>
>>>> ///////////////////////
>>>> // Find all partitions of n
>>>> ///////////////////////
>>>>
>>>>   def getParts(n:Int) : List[Partition] = {
>>>>
>>>>     ///////////////////////
>>>>     // Find all partitions of n using natural numbers at most as large
>>>> as
>>>> k
>>>>     //
>>>>     // (inspired by, but different from
>>>>     //
>>>> http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
>>>> )
>>>>     ///////////////////////
>>>>
>>>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>>>       if (k == 1)  // Stopping condition:
>>>>         List(new Partition(ones(n)))
>>>>       else if (k == n) // Special case to produce Partition(n) as a
>>>> partition
>>>>         List(new Partition(n)) ::: getParts2(k-1,n)
>>>>       else {
>>>>         // find all partitions which start with k
>>>>         val temp = getParts2(Math.min(k,n-k),n-k)
>>>>         val parts_k = temp map (p => new Partition(k,p))
>>>>
>>>>         // find all partitions using numbers at most as large as k-1
>>>>         val parts_k_1 = getParts2(k-1,n)
>>>>
>>>>         // put these lists together
>>>>         parts_k ::: parts_k_1
>>>>       }
>>>>     }
>>>>
>>>>     if (n < 0)
>>>>       emptyPartList  // by def
>>>>     if (n == 0)
>>>>       List(new Partition(0))  // by def (and the code above doesn't
>>>> handle
>>>> this)
>>>>     else
>>>>       getParts2(n,n)
>>>>
>>>>   }
>>>>
>>>>   //////////////////////
>>>>
>>>>   def getPartsMemo(n:Int) : List[Partition] = {
>>>>
>>>>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>>>>
>>>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>>>       if (!parts2map.contains((k,n))) {
>>>>         if (k == 1)
>>>>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>>>>         else if (k == n) {
>>>>           parts2map += ((k,n) -> (List(new Partition(n)) :::
>>>> getParts2(k-1,n)))
>>>>         }
>>>>         else {
>>>>           val temp = getParts2(Math.min(k,n-k),n-k)
>>>>           val parts_k = temp map (p => new Partition(k,p))
>>>>           val parts_k_1 = getParts2(k-1,n)
>>>>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>>>>         }
>>>>       }
>>>>       parts2map((k,n))
>>>>     }
>>>>
>>>>     if (n < 0)
>>>>       emptyPartList
>>>>     if (n == 0)
>>>>       List(new Partition(0))
>>>>     else
>>>>       getParts2(n,n)
>>>>
>>>>   }
>>>> }
>>>>
>>>>
>>>
>>>
>>> -----
>>> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
>>> http://eastsun.javaeye.com/category/34059 Click here
>>> --
>>> View this message in context:
>>> http://old.nabble.com/code-question-and-challenge-tp26153489p26155430.html
>>> Sent from the Scala - User mailing list archive at Nabble.com.
>>>
>>>
>>
>>
>
>
> -----
> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
> http://eastsun.javaeye.com/category/34059 Click here
> --
> View this message in context: http://old.nabble.com/code-question-and-challenge-tp26153489p26157761.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>

[Eastsun]

A new version:

scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
     |     val nums = new Array[Int](n+1)
     |     nums(0) = n
     |     var end = 1
     |
     |     override def hasNext = end <= n
     |
     |     override def next: List[Int] = {
     |         if(!hasNext) Iterator.empty.next
     |         val res = nums.slice(0,end).toList
     |         var idx = nums.lastIndexWhere{ _ > 1 }
     |         if(idx == -1){
     |             end = n + 1
     |             return res
     |         }
     |         nums(idx) -= 1
     |         var sum = nums.slice(idx+1,end).foldLeft(1){ _+_ }
     |         val num = nums(idx)
     |         do {
     |             idx += 1
     |             nums(idx) = num min sum
     |             sum -= num
     |         }while(sum > 0)
     |         end = idx + 1
     |         res
     |     }
     | }
defined class PartsItr

scala> new PartsItr(8) foreach println
List(8)
List(7, 1)
List(6, 2)
List(6, 1, 1)
List(5, 3)
List(5, 2, 1)
List(5, 1, 1, 1)
List(4, 4)
List(4, 3, 1)
List(4, 2, 2)
List(4, 2, 1, 1)
List(4, 1, 1, 1, 1)
List(3, 3, 2)
List(3, 3, 1, 1)
List(3, 2, 2, 1)
List(3, 2, 1, 1, 1)
List(3, 1, 1, 1, 1, 1)
List(2, 2, 2, 2)
List(2, 2, 2, 1, 1)
List(2, 2, 1, 1, 1, 1)
List(2, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1)

Kevin Squire wrote:

Eastsun,

That's clever.  One problem, though, is that it does not currently
preserve the order of the generated partitions, which I need.

(Technically, the list of partitions form a dominance order (partial
order), which I haven't quite determined how to deal with conceptually
in the application I'm targeting.)

Kevin

On Sun, Nov 1, 2009 at 5:42 PM, Eastsun <[e-mail]> wrote:
>
> How about this::working:
>
> C:\Documents and Settings\Admin>scala
> Welcome to Scala version 2.8.0.r19155-b20091020023404 (Java HotSpot(TM)
> Client VM, Java 1.6.0_16).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> class PartsItr(n: Int) extends Iterator[List[Int]] {
>     |     val nums = new Array[Int](n+1)
>     |     nums(0) = n
>     |     var end = 1
>     |
>     |     override def hasNext = end <= n
>     |
>     |     override def next: List[Int] = {
>     |         if(!hasNext) Iterator.empty.next
>     |         val res = nums.view.slice(0,end).toList
>     |         var (fst,sec) = (end-1,end)
>     |         while(fst >= 0 && nums(fst)-1 <= nums(fst+1)) fst -= 1
>     |         if(fst >= 0) sec = fst + 1
>     |         else         fst = nums.lastIndexWhere{ _ >= 2 }
>     |         if(sec == end) end += 1
>     |         if(end <= n) {
>     |             nums(sec) += 1
>     |             nums(fst) -= 1
>     |         }
>     |         res
>     |     }
>     | }
> defined class PartsItr
>
> scala> val itr = new PartsItr(100000)
> itr: PartsItr = non-empty iterator
>
> scala> val first100 = itr take 100
> first100: Iterator[List[Int]] = non-empty iterator
>
> scala> first100 foreach println
> List(100000)
> List(99999, 1)
> List(99998, 2)
> List(99998, 1, 1)
> List(99997, 2, 1)
> List(99996, 3, 1)
> List(99996, 2, 2)
> List(99996, 2, 1, 1)
> List(99995, 3, 1, 1)
> List(99995, 2, 2, 1)
> List(99994, 3, 2, 1)
> List(99993, 4, 2, 1)
> List(99993, 3, 3, 1)
> List(99993, 3, 2, 2)
> List(99993, 3, 2, 1, 1)
> List(99992, 4, 2, 1, 1)
> List(99992, 3, 3, 1, 1)
> List(99992, 3, 2, 2, 1)
> List(99991, 4, 2, 2, 1)
> List(99991, 3, 3, 2, 1)
> List(99990, 4, 3, 2, 1)
> List(99989, 5, 3, 2, 1)
> List(99989, 4, 4, 2, 1)
> List(99989, 4, 3, 3, 1)
> List(99989, 4, 3, 2, 2)
> List(99989, 4, 3, 2, 1, 1)
>
>
> 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
>>
>> ------------
>>
>> import scala.collection.mutable.Map
>>
>> // Partition class
>>
>> class Partition (val part: List[Int]) {
>>     def this(v: Int*) = this(v toList)
>>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>>
>>     override def toString = part.mkString("Partition(",", ",")")
>> }
>>
>> object Partition {
>>
>>   implicit def partWrapper(p: Partition): List[Int] = p.part
>>
>>   val emptyPartList = List[Partition]()
>>
>>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>>
>> ///////////////////////
>> // Find all partitions of n
>> ///////////////////////
>>
>>   def getParts(n:Int) : List[Partition] = {
>>
>>     ///////////////////////
>>     // Find all partitions of n using natural numbers at most as large as
>> k
>>     //
>>     // (inspired by, but different from
>>     //
>> http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
>> )
>>     ///////////////////////
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (k == 1)  // Stopping condition:
>>         List(new Partition(ones(n)))
>>       else if (k == n) // Special case to produce Partition(n) as a
>> partition
>>         List(new Partition(n)) ::: getParts2(k-1,n)
>>       else {
>>         // find all partitions which start with k
>>         val temp = getParts2(Math.min(k,n-k),n-k)
>>         val parts_k = temp map (p => new Partition(k,p))
>>
>>         // find all partitions using numbers at most as large as k-1
>>         val parts_k_1 = getParts2(k-1,n)
>>
>>         // put these lists together
>>         parts_k ::: parts_k_1
>>       }
>>     }
>>
>>     if (n < 0)
>>       emptyPartList  // by def
>>     if (n == 0)
>>       List(new Partition(0))  // by def (and the code above doesn't handle
>> this)
>>     else
>>       getParts2(n,n)
>>
>>   }
>>
>>   //////////////////////
>>
>>   def getPartsMemo(n:Int) : List[Partition] = {
>>
>>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>>
>>     def getParts2(k: Int, n: Int): List[Partition] = {
>>       if (!parts2map.contains((k,n))) {
>>         if (k == 1)
>>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>>         else if (k == n) {
>>           parts2map += ((k,n) -> (List(new Partition(n)) :::
>> getParts2(k-1,n)))
>>         }
>>         else {
>>           val temp = getParts2(Math.min(k,n-k),n-k)
>>           val parts_k = temp map (p => new Partition(k,p))
>>           val parts_k_1 = getParts2(k-1,n)
>>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>>         }
>>       }
>>       parts2map((k,n))
>>     }
>>
>>     if (n < 0)
>>       emptyPartList
>>     if (n == 0)
>>       List(new Partition(0))
>>     else
>>       getParts2(n,n)
>>
>>   }
>> }
>>
>>
>
>
> -----
> My scala solutions for  http://projecteuler.net/ Project Euler  problems:
> http://eastsun.javaeye.com/category/34059 Click here
> --
> View this message in context: http://old.nabble.com/code-question-and-challenge-tp26153489p26155430.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>

[Tony Morris-4]

// Avoiding requirement 1) for reasons unstated.
object Partition {
  def partition(a: Int) = {
    def pn(n: Int, as: List[List[Int]]): List[List[Int]] = as match {
      case Nil => Nil
      case h :: t => {
        lazy val s = (0 /: h)(_ + _)
        val y: List[List[Int]] => List[List[Int]] =
          if(s < n)
            _ ::: pn(n, h.head until n map (_ :: h) toList)
          else if(s > n)
            identity
          else
            h :: _
          y(pn(n, t))
      }
    }

    pn(a, 1 to a map (List(_)) toList)
  }

  def main(args: Array[String]) {
    List(5, 2, 6) map partition foreach println
  }
}

/*
  List(List(5), List(3, 2), List(4, 1), List(2, 2, 1), List(3, 1, 1),
List(2, 1, 1, 1), List(1, 1, 1, 1, 1))
  List(List(2), List(1, 1))
  List(List(6), List(3, 3), List(4, 2), List(2, 2, 2), List(5, 1),
List(3, 2, 1), List(4, 1, 1), List(2, 2, 1, 1), List(3, 1, 1, 1),
List(2, 1, 1, 1, 1), List(1, 1, 1, 1, 1, 1))
*/

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
>
> ------------
>
> import scala.collection.mutable.Map
>
> // Partition class
>
> class Partition (val part: List[Int]) {
>     def this(v: Int*) = this(v toList)
>     def this(v: Int, subPart: List[Int]) = this(v :: subPart)
>
>     override def toString = part.mkString("Partition(",", ",")")
> }
>
> object Partition {
>
>   implicit def partWrapper(p: Partition): List[Int] = p.part
>
>   val emptyPartList = List[Partition]()
>
>   def ones(n: Int) = (for (x <- 1 to n) yield 1) toList
>
> ///////////////////////
> // Find all partitions of n
> ///////////////////////
>
>   def getParts(n:Int) : List[Partition] = {
>
>     ///////////////////////
>     // Find all partitions of n using natural numbers at most as large as k
>     //
>     // (inspired by, but different from
>     //  http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function
> )
>     ///////////////////////
>
>     def getParts2(k: Int, n: Int): List[Partition] = {
>       if (k == 1)  // Stopping condition:
>         List(new Partition(ones(n)))
>       else if (k == n) // Special case to produce Partition(n) as a partition
>         List(new Partition(n)) ::: getParts2(k-1,n)
>       else {
>         // find all partitions which start with k
>         val temp = getParts2(Math.min(k,n-k),n-k)
>         val parts_k = temp map (p => new Partition(k,p))
>
>         // find all partitions using numbers at most as large as k-1
>         val parts_k_1 = getParts2(k-1,n)
>
>         // put these lists together
>         parts_k ::: parts_k_1
>       }
>     }
>
>     if (n < 0)
>       emptyPartList  // by def
>     if (n == 0)
>       List(new Partition(0))  // by def (and the code above doesn't handle this)
>     else
>       getParts2(n,n)
>
>   }
>
>   //////////////////////
>
>   def getPartsMemo(n:Int) : List[Partition] = {
>
>     var parts2map = Map[Tuple2[Int,Int], List[Partition]]()
>
>     def getParts2(k: Int, n: Int): List[Partition] = {
>       if (!parts2map.contains((k,n))) {
>         if (k == 1)
>           parts2map += ((k,n) -> List(new Partition(ones(n))))
>         else if (k == n) {
>           parts2map += ((k,n) -> (List(new Partition(n)) ::: getParts2(k-1,n)))
>         }
>         else {
>           val temp = getParts2(Math.min(k,n-k),n-k)
>           val parts_k = temp map (p => new Partition(k,p))
>           val parts_k_1 = getParts2(k-1,n)
>           parts2map += ((k,n) -> (parts_k ::: parts_k_1))
>         }
>       }
>       parts2map((k,n))
>     }
>
>     if (n < 0)
>       emptyPartList
>     if (n == 0)
>       List(new Partition(0))
>     else
>       getParts2(n,n)
>
>   }
> }
>
>  

--
Tony Morris
http://tmorris.net/