partitionsIterator: Partition/Composition Iterator

In RcppAlgos: High Performance Tools for Combinatorics and Computational Mathematics

Partition/Composition Iterator

Description

• Returns an iterator for iterating over partitions/compositions of a numbers.

• Supports random access via the [[ method.

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

• Use the next methods to obtain results in lexicographical order.

Usage

partitionsIter(v, m = NULL, repetition = FALSE,
               freqs = NULL, target = NULL,
               nThreads = NULL, tolerance = NULL)

compositionsIter(v, m = NULL, repetition = FALSE, freqs = NULL,
                 target = NULL, weak = FALSE, 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).
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.
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.

Details

Once you initialize a new iterator, the following methods are available:

nextIter

Retrieve the next lexicographical result

nextNIter

Pass an integer n to retrieve the next n lexicographical results

nextRemaining

Retrieve all remaining lexicographical results

currIter

Returns the current iteration

startOver

Resets the iterator

sourceVector

View the source vector

summary

Returns a list of summary information about the iterator

front

Retrieve the first lexicographical result

back

Retrieve the last lexicographical result

[[

Random access method. Pass a single value or a vector of valid indices. If a single value is passed, the internal index of the iterator will be updated, however if a vector is passed the internal state will not change. GMP support allows for flexible indexing.

Value

• If nextIter is called, a vector is returned

• Otherwise, a matrix with m columns

Note

• If nThreads is utilized, it will only take effect if the number of elements requested is greater than some threshold (determined internally). E.g:

  serial   <- partitionsIter(1000, 10)
  multi    <- partitionsIter(1000, 10, nThreads = 4)
  fetch1e6 <- multi@nextNIter(1e6)  ## much faster than serial@nextNIter(1e6)
  fetch1e3 <- multi@nextNIter(1e3)  ## only one thread used... same as serial@nextNIter(1e3)
  
  library(microbenchmark)
  microbenchmark(multi@nextNIter(1e6), serial@nextNIter(1e6))
  microbenchmark(multi@nextNIter(1e3), serial@nextNIter(1e3))

• 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.

  • If the source vector is not isomorphic to 1:length(v)

• The maximum number of partitions/compositions that can be generated at one time is 2^{31} - 1.

Author(s)

Joseph Wood

References

• Lexicographical Order

• Subset Sum Problem

• Partition (number theory)

• Composition (combinatorics))

See Also

partitionsGeneral, compositionsGeneral

Examples

a = partitionsIter(0:10, repetition = TRUE)
a@nextIter()
a@nextNIter(3)
a@front()
a@nextRemaining()
a@summary()
a@back()
a[[5]]
a@summary()
a[[c(1, 17, 3)]]
a@summary()

## Multisets... no random access
b = partitionsIter(40, 5, freqs = rep(1:4, 10), target = 80)
b@nextIter()
b@nextNIter(10)
b@summary()
b@nextIter()
b@currIter()

RcppAlgos documentation built on Oct. 3, 2023, 1:07 a.m.