partitionsIterator: Partition/Composition Iterator In RcppAlgos: High Performance Tools for Combinatorics and Computational Mathematics

 partitionsIter R Documentation

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

Joseph Wood

References

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