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 was born 19965 days, 16 hours, 55 minutes ago.