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 19967 days, 6 hours, 12 minutes ago.