partitionsGeneral {RcppAlgos}

Generate Partitions/Compositions

Description

The algorithms in RcppAlgos go beyond the traditional integer partition algorithms and can tackle a wide variety of cases.

• Efficient algorithms for partitioning numbers under various constraints:

  • Standard (with repetition)

  • Distinct

  • Restricted

  • Where each part has a specific multiplicity (i.e. when using freqs for multisets).

  • Arbitrary target and source vector (e.g. partitionsGeneral(sample(1000, 20), 10, TRUE, target = 5000))

• Produce results in parallel using the nThreads arguments.

• Alternatively, the arguments lower and upper make it possible to generate partitions/compositions in chunks allowing for parallelization via the parallel package.

• GMP support allows for exploration of cases where the number of partitions/compositions is large.

• The output is in lexicographical order.

Usage

partitionsGeneral(v, m = NULL, ...)
compositionsGeneral(v, m = NULL, ...)

## Default S3 method:
partitionsGeneral(
    v, m = NULL, repetition = FALSE, freqs = NULL, target = NULL,
    lower = NULL, upper = NULL, nThreads = NULL, tolerance = NULL, ...
)
## Default S3 method:
compositionsGeneral(
    v, m = NULL, repetition = FALSE, freqs = NULL, target = NULL, weak = FALSE,
    lower = NULL, upper = NULL, nThreads = NULL, tolerance = NULL, ...
)

## S3 method for class 'table'
partitionsGeneral(
    v, m = NULL, target = NULL, lower = NULL,
    upper = NULL, nThreads = NULL, tolerance = NULL, ...
)
## S3 method for class 'table'
compositionsGeneral(
    v, m = NULL, target = NULL, weak = FALSE, lower = NULL,
    upper = NULL, nThreads = NULL, tolerance = NULL, ...
)

Arguments

v

Source vector. If v is a positive integer, it will be converted to the sequence 1:v. If v is a negative integer, it will be converted to the sequence v:-1. Only integer and numeric vectors are accepted.

m

Width of the partition. If m = NULL, the length will be determined by the partitioning case (e.g. When we are generating distinct partitions of n, the width will be equal to the smallest m such that sum(1:m) >= n).

...

Further arguments passed to methods.

repetition

Logical value indicating whether partitions/compositions should be with or without repetition. The default is FALSE.

freqs

A vector of frequencies used for producing all partitions of a multiset of v. Each element of freqs represents how many times each element of the source vector, v, is repeated. It is analogous to the times argument in rep. The default value is NULL.

lower

The lower bound. Partitions/compositions are generated lexicographically, thus utilizing this argument will determine which specific partition to start generating from (e.g. partitionsGeneral(15, 3, lower = 6) is equivalent to partitionsGeneral(15, 3)[6:partitionsCount(15, 3), ]). This argument along with upper is very useful for generating partitions/compositions in chunks allowing for easy parallelization.

upper

The upper bound. Similar to lower, however this parameter allows the user to stop generation at a specific partition (e.g. partitionsGeneral(15, 3, upper = 5) is equivalent to partitionsGeneral(15, 3)[1:5, ])

target

Number to be partitioned. If NULL, max(v) will be used.

weak

(Compositions only) Logical flag indicating whether to allow terms of the sequence to be zero.

nThreads

Specific number of threads to be used. The default is NULL.

tolerance

A numeric value greater than or equal to zero. This parameter is utilized when a constraint is applied on a numeric vector. The default value is 0 when it can be determined that whole values are being utilized, otherwise it is sqrt(.Machine$double.eps) which is approximately 1.5e-8. N.B. If the input vector is of type integer, this parameter will be ignored and strict equality will be enforced.

Value

A matrix is returned with each row containing a vector of length m.

Note

• nThreads will be ignored in the following cases (i.e. Generating the n^{th} partition in these cases are currently unavailable):

  • With standard multisets. If zero is the only element with a non-trivial multiplicity, multithreading is possible (e.g. partitionsGeneral(0:100, freqs = c(100, rep(1, 100)), nThreads = 4)).

  • If the source vector is not isomorphic to 1:length(v) (e.g. v = c(1, 4, 6, 7, 8)).

• The maximum number of partitions/compositions that can be generated at one time is 2^{31} - 1. Utilizing lower and upper makes it possible to generate additional partitions/compositions.

Author(s)

Joseph Wood

References

• Lexicographical Order

• Subset Sum Problem

• Partition (number theory)

• Composition (combinatorics))

Examples

partitionsGeneral(1)
partitionsGeneral(-1:0, 1)
partitionsGeneral(-1:0, 1, target = -1)
partitionsGeneral(20, 5)
partitionsGeneral(20, 5, repetition = TRUE)
partitionsGeneral(20, 5, freqs = rep(1:4, 5))
partitionsGeneral(20, 5, TRUE, target = 80)
partitionsGeneral(0:10, repetition = TRUE)
partitionsGeneral(seq(2L, 500L, 23L), 5, target = 1804)

compositionsGeneral(0:10, 5, repetition = TRUE)

set.seed(111)
partitionsGeneral(sample(1000, 20), 5, TRUE, target = 2500)

system.time(one_thread  <- partitionsGeneral(80, 10, TRUE))
system.time(two_threads <- partitionsGeneral(80, 10, TRUE, nThreads = 2))
identical(one_thread, two_threads)