Package de.tilman_neumann.jml.partitions

Class 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 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()
        Specified by:
        hasNext in interface Generator<Mpi[]>
        Returns:
        true if there is another partition

      • 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.
        Specified by:
        next in interface Generator<Mpi[]>
        Returns:
        next partition

      • 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