partitions.frink

View or download 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
}


View or download 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 was born 17591 days, 17 hours, 48 minutes ago.