Package de.tilman_neumann.jml.partitions
Class MpiPartitionGenerator
java.lang.Object
de.tilman_neumann.jml.partitions.MpiPartitionGenerator
public class MpiPartitionGenerator extends java.lang.Object implements Generator<Mpi[]>
A generator for the additive partitions of multipartite numbers.
This work started from the observation that the number of additive partitions of a multipartite number
q = [q1, q2, ..., qk] equals the number of essentially distinct factorizations of
a number N with prime factorization N = p1^q1 * p2^q2 * ... * pk^qk.
(see e.g. [Hughes, Shallit: "On the number of multiplicative partitions", 1983])
I began with a very slow implementation counting distinct factorizations, and having this as a reference, little by little
developed a second implementation working only with manipulations of multipartite numbers and partitions of them.
The latter turned out to be much, much faster. Single-threaded and on a modest computer, it is capable to
count several million of partitions per second.
The crucial ingredients to obtain such a speed were the use of a stack, and the PowerMap.
Notably, the complements of parts are never computed twice for any (rest, part) pair.
- See Also:
- Serialized Form
-
Constructor Summary
Constructors Constructor Description MpiPartitionGenerator(Mpi q)
Complete constructor for a generator of the partitions of the multivariate number q. -
Method Summary
Modifier and Type Method Description boolean
hasNext()
static void
main(java.lang.String[] args)
TestMpi[]
next()
Compute the next partition of the multipartite input.static long
numberOfFactorizationsOf(java.math.BigInteger n)
Computes the number of essentially different prime factorizations of n.static long
numberOfPartitionsOf(Mpi q)
Counts the number of partitions of the given multipartite integer.static java.util.SortedSet<MpiPartition>
partitionsOf(Mpi q)
Computes the partitions of the given multipartite number.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
MpiPartitionGenerator
Complete constructor for a generator of the partitions of the multivariate number q.- Parameters:
q
-
-
-
Method Details
-
hasNext
public boolean hasNext() -
next
Compute the next partition of the multipartite input. The result is a flat array of parts because this is much faster than creating multisets. -
partitionsOf
Computes the partitions of the given multipartite number.- Parameters:
q
- the multipartite number [q_1, q_2, ...]- Returns:
- partitions = SortedSet
, partition = MpiPartition, part = Mpi
-
numberOfPartitionsOf
Counts the number of partitions of the given multipartite integer.- Parameters:
q
-- Returns:
- number of partitions of q
-
numberOfFactorizationsOf
public static long numberOfFactorizationsOf(java.math.BigInteger n)Computes the number of essentially different prime factorizations of n.- Parameters:
n
-- Returns:
- number of essentially different prime factorizations of n
-
main
public static void main(java.lang.String[] args)Test- Parameters:
args
- ignored
-