Package de.tilman_neumann.jml.partitions
Class MpiPartitionGenerator
- java.lang.Object
-
- de.tilman_neumann.jml.partitions.MpiPartitionGenerator
-
- All Implemented Interfaces:
Generator<Mpi[]>
,Serializable
public class MpiPartitionGenerator extends 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.- Author:
- Tilman Neumann
- 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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
hasNext()
static void
main(String[] args)
TestMpi[]
next()
Compute the next partition of the multipartite input.static long
numberOfFactorizationsOf(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 SortedSet<MpiPartition>
partitionsOf(Mpi q)
Computes the partitions of the given multipartite number.
-
-
-
Constructor Detail
-
MpiPartitionGenerator
public MpiPartitionGenerator(Mpi q)
Complete constructor for a generator of the partitions of the multivariate number q.- Parameters:
q
-
-
-
Method Detail
-
hasNext
public boolean hasNext()
-
next
public Mpi[] 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
public static SortedSet<MpiPartition> partitionsOf(Mpi q)
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
public static long numberOfPartitionsOf(Mpi q)
Counts the number of partitions of the given multipartite integer.- Parameters:
q
-- Returns:
- number of partitions of q
-
numberOfFactorizationsOf
public static long numberOfFactorizationsOf(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(String[] args)
Test- Parameters:
args
- ignored
-
-