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 2 3 ## And the next a$nextIter()
 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
 "Combinations of 5 choose 3"

$currentIndex  11$totalResults
 10

$totalRemaining  -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)

 FALSE

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

## As in the previous example, we set the current iterator to a variable
iter = a$currIter() ## Defined above print(i)  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
 "Combinations of 5 choose 3"

$currentIndex  0$totalResults
 10

$totalRemaining  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  "Combinations of 5 choose 3"$currentIndex
 4

$totalResults  10$totalRemaining
 6

## View the current combination
a$currIter()  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
 "Combinations of 5 choose 3"

$currentIndex  11$totalResults
 10

$totalRemaining  -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
 "Combinations of 5 choose 3"

$currentIndex  7$totalResults
 10

$totalRemaining  3 ## View the current combination a$currIter()
 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  "Combinations of 5 choose 3"$currentIndex
 0

$totalResults  10$totalRemaining
 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  10 ## Let's get the 3rd combination a[]  1 2 5 ## See the summary. Note that the index has been updated a$summary()
$description  "Combinations of 5 choose 3"$currentIndex
 3

$totalResults  10$totalRemaining
 7

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

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

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

$currentIndex  10$totalResults
 10

$totalRemaining  0 a$currIter()
 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[]
 1 2 4

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

$currentIndex  2$totalResults
 10

$totalRemaining  8 set.seed(121) samp = sample(a$summary()$totalResults, 4) samp  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  "Combinations of 5 choose 3"$currentIndex
 2

$totalResults  10$totalRemaining
 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()  "ABC" b$nextNIter(5)
[]
 "ABD"

[]
 "ACB"

[]
 "ACD"

[]

[]

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

$totalResults  24$totalRemaining
 0

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

[]
 "DBA"

[]
 "DAC"

[]
 "DAB"

[]
 "CDB"

b$nextRemaining() []  "DAB" []  "DAC" []  "DBA" []  "DBC" []  "DCA" []  "DCB" ## Random access a[]  "ADB" b$prevRemaining()
[]
 "ACD"

[]
 "ACB"

[]
 "ABD"

[]
 "ABC"

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