# Combinatorial Iterators in RcppAlgos

#### 3/19/2019

This document covers working with combinatorial iterators in RcppAlgos. Combinatorial iterators in RcppAlgos are memory efficient like traditional iterator objects. They allow traversal of combinations/permutations one by one without the necessity for storing all results in memory.

Unlike traditional combinatorial iterators, the iterators in RcppAlgos offers random access via the [[ operator. This means, we can access the nth lexicographical order result on demand without having to first iterate over the previous n - 1 results.

## Iterating over Combinations and Permutations

In order to iterate, we must initialize an iterator via comboIter or permuteIter. The interface is very similar to comboGeneral and permuteGeneral.

library(RcppAlgos)

## Initialize the iterator
a = comboIter(5, 3)

## Get the first combination
a$nextIter() [1] 1 2 3 ## And the next a$nextIter()
[1] 1 2 4

## Set the current iterator to a variable
iter = a$currIter() i = 1 ## Iterate until there are no more while (!isFALSE(iter)) { cat(i, " ", iter, "\n") iter = a$nextIter()
i = i + 1
}
1   1 2 4
2   1 2 5
3   1 3 4
4   1 3 5
5   1 4 5
6   2 3 4
7   2 3 5
8   2 4 5
9   3 4 5
No more results. To see the last result, use the prevIter method(s)

## See the output of comboGeneral for comparison
comboGeneral(5, 3, lower = 2)
[,1] [,2] [,3]
[1,]    1    2    4
[2,]    1    2    5
[3,]    1    3    4
[4,]    1    3    5
[5,]    1    4    5
[6,]    2    3    4
[7,]    2    3    5
[8,]    2    4    5
[9,]    3    4    5

## Call the summary method to see information about our iterator
a$summary()$description
[1] "Combinations of 5 choose 3"

$currentIndex [1] 11$totalResults
[1] 10

$totalRemaining [1] -1 ## Bidirectional Iterators The standard combinatorial iterators in RcppAlgos are bidirectional iterators. This means that not only can we iterate in a forward manner (i.e. lexicographically), but we can also iterate backwards (i.e. Reverse Lexicographical Order) via the prevIter method(s). ## Using the same iterable from the previous section a$currIter()
No more results. To see the last result, use the prevIter method(s)

[1] FALSE

## As the comment says, we call the prevIter method to see the last result
a$prevIter() [1] 3 4 5 ## Get the previous result a$prevIter()
[1] 2 4 5

## As in the previous example, we set the current iterator to a variable
iter = a$currIter() ## Defined above print(i) [1] 10 ## Iterate until we are at the very beginning. Note that the ## output is exactly the same as above, but in reverse order while (!isFALSE(iter)) { i = i - 1 cat(i, " ", iter, "\n") iter = a$prevIter()
}
9   2 4 5
8   2 3 5
7   2 3 4
6   1 4 5
5   1 3 5
4   1 3 4
3   1 2 5
2   1 2 4
1   1 2 3
Iterator Initialized. To see the first result, use the nextIter method(s)

## Call the summary method to see information about our iterator
a$summary()$description
[1] "Combinations of 5 choose 3"

$currentIndex [1] 0$totalResults
[1] 10

$totalRemaining [1] 10 ## Retrieving More than One Result at a Time There are four methods which allow for obtaining more than one result at a time: nextNIter, prevNIter, nextRemaining, and prevRemaining. ## Reset the iterator a$startOver

## Get the next 4 combinations
a$nextNIter(4) [,1] [,2] [,3] [1,] 1 2 3 [2,] 1 2 4 [3,] 1 2 5 [4,] 1 3 4 ## Get the summary. Note that the index has been updated a$summary()
$description [1] "Combinations of 5 choose 3"$currentIndex
[1] 4

$totalResults [1] 10$totalRemaining
[1] 6

## View the current combination
a$currIter() [1] 1 3 4 ## Get the remaining combinations with nextRemaining a$nextRemaining()
[,1] [,2] [,3]
[1,]    1    3    5
[2,]    1    4    5
[3,]    2    3    4
[4,]    2    3    5
[5,]    2    4    5
[6,]    3    4    5

a$summary()$description
[1] "Combinations of 5 choose 3"

$currentIndex [1] 11$totalResults
[1] 10

$totalRemaining [1] -1 Now, we look at the opposite direction. ## Get the previous 4 combinations a$prevNIter(4)
[,1] [,2] [,3]
[1,]    3    4    5
[2,]    2    4    5
[3,]    2    3    5
[4,]    2    3    4

## Get the summary. Note that the index has been updated
a$summary()$description
[1] "Combinations of 5 choose 3"

$currentIndex [1] 7$totalResults
[1] 10

$totalRemaining [1] 3 ## View the current combination a$currIter()
[1] 2 3 4

## Get the remaining previous combinations with prevRemaining
a$prevRemaining() [,1] [,2] [,3] [1,] 1 4 5 [2,] 1 3 5 [3,] 1 3 4 [4,] 1 2 5 [5,] 1 2 4 [6,] 1 2 3 a$summary()
$description [1] "Combinations of 5 choose 3"$currentIndex
[1] 0

$totalResults [1] 10$totalRemaining
[1] 10

## Random Access Iterator

For standard combinatorial iterators in RcppAlgos, we can jump to the nth combination/permutation without the need for iterating over the first n - 1 results.

## Reset the iterator
a$startOver() ## How many total combinations do we have? a$summary()$totalResults [1] 10 ## Let's get the 3rd combination a[[3]] [1] 1 2 5 ## See the summary. Note that the index has been updated a$summary()
$description [1] "Combinations of 5 choose 3"$currentIndex
[1] 3

$totalResults [1] 10$totalRemaining
[1] 7

## Let's see the 9th combination
a[[9]]
[1] 2 4 5

## What about the first and last combination?
a$front() [1] 1 2 3 a$back()
[1] 3 4 5

## Again the index has been updated
a$summary()$description
[1] "Combinations of 5 choose 3"

$currentIndex [1] 10$totalResults
[1] 10

$totalRemaining [1] 0 a$currIter()
[1] 3 4 5

We can also easily return a random sample of combinations with the [[ operator by passing a vector of indices. In these cases, it should be noted that the current index will not be updated.

## Set the current index to the second combination
a[[2]]
[1] 1 2 4

a$summary()$description
[1] "Combinations of 5 choose 3"

$currentIndex [1] 2$totalResults
[1] 10

$totalRemaining [1] 8 set.seed(121) samp = sample(a$summary()$totalResults, 4) samp [1] 4 7 10 1 a[[samp]] [,1] [,2] [,3] [1,] 1 3 4 [2,] 2 3 4 [3,] 3 4 5 [4,] 1 2 3 ## Note that the current index remains unchanged a$summary()
$description [1] "Combinations of 5 choose 3"$currentIndex
[1] 2

$totalResults [1] 10$totalRemaining
[1] 8

## User Defined Functions

Just as with comboGeneral and permuteGeneral, we can pass a user defined function to comboIter and permuteIter.

## Initialize the iterator
b = permuteIter(LETTERS[1:4], 3, FUN = function(p) paste(p, collapse = ""))

b$nextIter() [1] "ABC" b$nextNIter(5)
[[1]]
[1] "ABD"

[[2]]
[1] "ACB"

[[3]]
[1] "ACD"

[[4]]

[[5]]

b$back() [1] "DCB" b$summary()
$description [1] "Permutations of 4 choose 3"$currentIndex
[1] 24

$totalResults [1] 24$totalRemaining
[1] 0

b$prevIter() [1] "DCA" b$prevNIter(5)
[[1]]
[1] "DBC"

[[2]]
[1] "DBA"

[[3]]
[1] "DAC"

[[4]]
[1] "DAB"

[[5]]
[1] "CDB"

b$nextRemaining() [[1]] [1] "DAB" [[2]] [1] "DAC" [[3]] [1] "DBA" [[4]] [1] "DBC" [[5]] [1] "DCA" [[6]] [1] "DCB" ## Random access a[[5]] [1] "ADB" b$prevRemaining()
[[1]]
[1] "ACD"

[[2]]
[1] "ACB"

[[3]]
[1] "ABD"

[[4]]
[1] "ABC"

## View the source vector
b\$sourceVector()
[1] "A" "B" "C" "D"