Class MpiPartitionGenerator

java.lang.Object
de.tilman_neumann.jml.partitions.MpiPartitionGenerator
All Implemented Interfaces:
Generator<Mpi[]>, java.io.Serializable

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)
    Test
    Mpi[] 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

      public MpiPartitionGenerator​(Mpi q)
      Complete constructor for a generator of the partitions of the multivariate number q.
      Parameters:
      q -
  • Method Details

    • 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 java.util.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​(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