partitions.frink

Download or view partitions.frink in plain text format


// Returns all the partitions of an integer.
// NOTE: This class is no longer necessary as Frink now has a built-in
// partitions function.
// 
// The algorithm is Algorithm P from Knuth's 7.2.1.4
partitionInteger[n] :=
{
   a = new array[]              // Array of size n+1
   results = new array
   
   a@0 = 0
   m = 1
   count = 0

   // Step P2
   a@m = n
   q = m - (n==1 ? 1 : 0)

   do
   {
      // Step P3... dump the partition.
      // This would be a good place for a "yield" statement.
      results.push[sliceLength[a,1,m]]
      count = count + 1

      if a@q == 2
      {
         // Step P4
         a@q = 1
         q = q - 1
         m = m + 1
         a@m = 1
      } else
      {
         // Step P5
         if q == 0
            return results

         x = a@q - 1
         a@q = x
         n = m-q+1
         m = q + 1

         while (n > x)
         {
            a@m = x
            m = m + 1
            n = n - x
         }

         // Simulate Step P2
         a@m = n
         q = m - (n==1 ? 1 : 0)
      }
   } while (true)

   return results
}


Download or view partitions.frink in plain text format

This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen, eliasen@mindspring.com