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.
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] -1The 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] 10There 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] -1Now, 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] 10For 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 5We 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] 8Just 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]]
[1] "ADB"
[[5]]
[1] "ADC"
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"