---
title: "Combinatorial Sampling and Ranking"
author: "Joseph Wood"
date: "2026-03-04"
output:
  prettydoc::html_pretty:
    theme: architect
    toc: true
    number_sections: false
vignette: >
  %\VignetteIndexEntry{Combinatorial Sampling and Ranking}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

This document covers topics in generating random samples of combinations, permutations, partitions, compositions and partition of groups. It is encouraged to read [General Combinatorics](<https://jwood000.github.io/RcppAlgos/articles/GeneralCombinatorics.html>) first.

------------------------------------------------------------------------

# Sampling

At the heart of sampling is the ability to efficiently generate the *n<sup>th</sup>* [lexicographical](<https://en.wikipedia.org/wiki/Lexicographic_order>) result. The algorithms in `RcppAlgos` are flexible and optimized, allowing for tackling this task with ease.

## Base R

To illustrate this in base R, let us consider getting 5 random combinations of the vector `1:20` of length 10. How should we proceed?

A naive approach would be to generate all of the combinations using `combn` and then call `sample`:

``` r
options(width = 90)
naive <- function(v, m, n, s) {
    allCombs <- combn(v, m)
    set.seed(s)
    allCombs[, sample(ncol(allCombs), n)]
}

fiveRndCombs <- naive(20, 10, 5, 42)
t(fiveRndCombs)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    1    3    5   10   11   14   15   16   18    20
#> [2,]    1    3    4    9   10   11   12   13   18    19
#> [3,]    2    3    4    6    9   10   12   13   15    19
#> [4,]    1    4    5   10   13   14   15   17   18    19
#> [5,]    1    3    4    5    7    8   13   15   18    19
```

This is okay for this small example (there are only `choose(20, 10) = 184756` results), however what if we wanted to find one hundred thousand random combinations from the vector `1:100` of length 20? Clearly, the approach above will not be feasible as there are far too many results to generate (`choose(100, 20) = 5.359834e+20`). Furthermore, there are internal limitations on `sample`. If we try to pass `choose(100, 20)`, we will get an error:

``` r
sample(choose(100, 20), 5)
#> Error in sample.int(x, size, replace, prob): invalid first argument
```

We could also try calling `sample(100, 20)` a bunch of times and hope we don’t get duplicate combinations. This is neither promising nor elegant.

------------------------------------------------------------------------

## RcppAlgos Solutions

`RcppAlgos` provides five functions: `comboSample`, `permuteSample`, `partitionsSample`, `compositionsSample`, and `comboGroupsSample` for seamlessly attacking these types of problems. All functions provide the following:

- Easily generate random samples in parallel using the `nThreads` or the `Parallel` parameters.
- You can pass a vector of specific indices via `sampleVec` or rely on the internal sampling functions. We call `sample` when the total number of results is small and for larger cases, the sampling is done in a very similar fashion to `urand.bigz` from the `gmp` package.
- Consistent interface to their respective general functions (e.g. `partitionsGeneral`)
- The `seed` parameter allows for generating reproducible samples.
- If the gmp library is needed, the `seed` parameter must be set in order to have reproducible results (*E.g.* `set.seed()`) has no effect in these cases).

## `comboSample` and `permuteSample`

Let’s first look at the first problem above (i.e. getting 5 random combinations of the vector `1:20` of length 10):

``` r
library(RcppAlgos)
set.seed(42)
comboSample(20, 10, n = 5)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    1    3    5   10   11   14   15   16   18    20
#> [2,]    1    3    4    9   10   11   12   13   18    19
#> [3,]    2    3    4    6    9   10   12   13   15    19
#> [4,]    1    4    5   10   13   14   15   17   18    19
#> [5,]    1    3    4    5    7    8   13   15   18    19

## Use the seed argument directly to produce the same output
comboSample(20, 10, n = 5, seed = 42)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    1    3    5   10   11   14   15   16   18    20
#> [2,]    1    3    4    9   10   11   12   13   18    19
#> [3,]    2    3    4    6    9   10   12   13   15    19
#> [4,]    1    4    5   10   13   14   15   17   18    19
#> [5,]    1    3    4    5    7    8   13   15   18    19

## fiveRndCombs produced above
identical(t(fiveRndCombs),
          comboSample(20, 10, n = 5, seed = 42))
#> [1] TRUE
```

### Samples of Results with Repetition

Just like with `comboGeneral` and `permuteGeneral`, we can explore results with repetition.

``` r
comboSample(10, 8, TRUE, n = 3, seed = 84)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    2    5    5    7    9    9    9    9
#> [2,]    4    5    8    8    8   10   10   10
#> [3,]    2    6    6    6    6    6    9    9

permuteSample(10, 8, TRUE, n = 3)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    4   10    4    4   10    2    2   10
#> [2,]    1    4    5   10    5    5    2    2
#> [3,]    4    1    7    9    1    5    6    5

comboSample(10, 12, freqs = 1:10, n = 3)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
#> [1,]    2    2    3    5    5    6    6    6    7     8     9    10
#> [2,]    1    2    3    3    5    5    6    7    9     9     9     9
#> [3,]    1    2    5    5    5    6    6    9   10    10    10    10

permuteSample(10, 12, freqs = 1:10, n = 3, seed = 123)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
#> [1,]    2    8    7    4    8    9   10   10    7     1     8     2
#> [2,]    5    5    9    8    1    8    3    2    6     4     3    10
#> [3,]   10    3    8    8    4    8    8    6   10     6     3     8
```

### Specific Results with `sampleVec`

We can also utilize `sampleVec` to generate specific results.

``` r
## E.g. the below generates the 1st, 5th, 25th, 125th, and
## 625th lexicographical combinations
comboSample(10, 8, TRUE, sampleVec = c(1, 5, 25, 125, 625))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    1    1    1    1    1    1
#> [2,]    1    1    1    1    1    1    1    5
#> [3,]    1    1    1    1    1    1    3    8
#> [4,]    1    1    1    1    1    3    6    9
#> [5,]    1    1    1    1    5    6   10   10

## Is the same as:
comboGeneral(10, 8, TRUE)[5^(0:4), ]
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    1    1    1    1    1    1
#> [2,]    1    1    1    1    1    1    1    5
#> [3,]    1    1    1    1    1    1    3    8
#> [4,]    1    1    1    1    1    3    6    9
#> [5,]    1    1    1    1    5    6   10   10
```

### Using `namedSample`

Have you ever wondered which lexicographical combinations/permutations are returned when sampling? No worries, simply set `namedSample = TRUE`:

``` r
testInd <- permuteSample(30, 10, n = 3, seed = 100, namedSample = TRUE)
testInd
#>                [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> 86626302070118   24   26    7   29    3   21   20    9   16    28
#> 15871916538841    5   12   21    9    6    3   14   23    4    20
#> 87932455980012   25    6   20   23   18   10   27   30   19    29

## Same output as above
permuteSample(30, 10, sampleVec = row.names(testInd))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]   24   26    7   29    3   21   20    9   16    28
#> [2,]    5   12   21    9    6    3   14   23    4    20
#> [3,]   25    6   20   23   18   10   27   30   19    29
```

### Parallel Computing and GMP Support

Just like the `General` counterparts, the sampling functions utilize GMP to allow for exploration of combinations/permutations of large vectors where the total number of results is enormous. They also offer parallel options using `Parallel` or `nThreads`.

``` r
## Uses min(stdThreadMax() - 1, 5) threads (in this case)
permuteSample(500, 10, TRUE, n = 5, seed = 123, Parallel = TRUE)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]   55  435  274  324  200  152    6  313  121   377
#> [2,]  196  166  331  154  443  329  155  233  354   442
#> [3,]  235  325   94   27  370  117  302   86  229   126
#> [4,]  284  104  464  104  207  127  117    9  390   414
#> [5,]  456   76  381  456  219   23  376  187   11   123

permuteSample(factor(state.abb), 15, n = 3, seed = 50, nThreads = 3)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15]
#> [1,] ME   FL   DE   OK   ND   CA   PA   AL   ID   MO    NM    HI    KY    MT    NJ   
#> [2,] AZ   CA   AL   CT   ME   SD   ID   SC   OK   NH    HI    TN    ND    IA    MT   
#> [3,] MD   MO   NC   MT   NH   AL   VA   MA   VT   WV    NJ    NE    MN    MS    MI   
#> 50 Levels: AK AL AR AZ CA CO CT DE FL GA HI IA ID IL IN KS KY LA MA MD ME MI MN MO ... WY

permuteCount(factor(state.abb), 15)
#> Big Integer ('bigz') :
#> [1] 2943352142120754524160000
```

### Efficiency

The algorithms are incredibly efficient and offer tremendous gains over the naive approach above:

``` r
## the function "naive" is defined above
system.time(naive(25, 10, 5, 15))
#>    user  system elapsed 
#>   1.001   0.012   1.014

system.time(comboSample(25, 10, n = 5, seed = 15))
#>    user  system elapsed 
#>   0.001   0.000   0.001
```

Even when dealing with extremely large numbers, these algorithms are very fast. And using the parallel options have even greater effects than we saw with the general counterparts (typically around \~2-3 times faster with the general functions, whereas with the last example below with sampling we see a nearly 5x improvement).

``` r
## Lightning fast even with examples involving many results
system.time(comboSample(2500, 100, n = 5, seed = 15))
#>    user  system elapsed 
#>       0       0       0

## The total number of combinations has ~180 digits
gmp::log10.bigz(comboCount(2500, 100))
#> [1] 180.9525

## Still fast with larger samples
system.time(comboSample(2500, 100, n = 1e4, seed = 157))
#>    user  system elapsed 
#>   0.401   0.001   0.402

## Using Parallel/nThreads in these cases has an even greater effect
system.time(comboSample(2500, 100, n = 1e4, seed = 157, nThreads = 8))
#>    user  system elapsed 
#>   0.591   0.003   0.085
```

### User Defined Functions

Again, just as with the general functions, you can pass a custom function to `{combo|permute}Sample` using the `FUN` argument.

``` r
permuteSample(5000, 1000, n = 3, seed = 101, FUN = sd)
#> [[1]]
#> [1] 1431.949
#> 
#> [[2]]
#> [1] 1446.859
#> 
#> [[3]]
#> [1] 1449.272

## Example using complex numbers
myCplx <- as.complex(1:100 + rep(c(-1, 1), 50) * 1i)

permuteSample(myCplx, 10, freqs = rep(1:5, 20),
              n = 3, seed = 101, FUN = function(x) {
                  sqrt(sum(x))
              })
#> [[1]]
#> [1] 24.83948+0i
#> 
#> [[2]]
#> [1] 20.9285+0.04778172i
#> 
#> [[3]]
#> [1] 22.20379+0.09007473i
```

## `partitionsSample`

The `partitionsSample` function allows one to draw a random sample of partitions of a number. Many of the features present in `comboSample` and `permuteSample` are available in `partitionsSample`.

``` r
## Use the seed parameter to obtain reproducible results
partitionsSample(100, 8, TRUE, n = 3, seed = 42)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    3    3    4   20   23   45
#> [2,]    1    1    2    7   14   14   29   32
#> [3,]    2   10   11   11   16   16   16   18

## Used namedSample to obtain the lexicographical indices
partitionsSample(100, 8, TRUE, n = 3, seed = 42, namedSample = TRUE)
#>        [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 61413     1    1    3    3    4   20   23   45
#> 54425     1    1    2    7   14   14   29   32
#> 623844    2   10   11   11   16   16   16   18

## Use sampleVec to obtain specific results
partitionsSample(100, 8, TRUE, sampleVec = c(61413, 54425, 623844))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    3    3    4   20   23   45
#> [2,]    1    1    2    7   14   14   29   32
#> [3,]    2   10   11   11   16   16   16   18

partitionsCount(2500, 10)
#> Big Integer ('bigz') :
#> [1] 2621914835336941325

## Algorithms are very efficient
system.time(serial <- partitionsSample(2500, 10, n = 1e3,
                                       seed = 8128))
#>    user  system elapsed 
#>   2.325   0.005   2.331

## Use nThreads for greater efficiency
system.time(multi <- partitionsSample(2500, 10, n = 1e3,
                                      seed = 8128, nThreads = 8))
#>    user  system elapsed 
#>   3.401   0.016   0.442

identical(multi, serial)
#> [1] TRUE

## Even works with non-standard setup
partitionsSample(17 + (1:10) * 3, 10, TRUE,
                 target = 320, n = 3, seed = 111)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]   23   23   26   26   29   29   38   38   41    47
#> [2,]   26   26   26   29   29   29   32   41   41    41
#> [3,]   20   23   23   26   26   35   38   41   44    44
```

There are sampling algorithms available for most partition cases, but some cases are not covered. For example, with standard multisets, we are currently unable to *efficiently* generate the *n<sup>th</sup>* lexicographical result. Another example is when the source vector is not uniform (*e.g.* when the distance between each element is irregular).

Observe the following:

``` r
## No sampling algorithm available when the source vector is not uniform
partitionsSample(c(1, 4, 6, 7, 10, seq(11, 100, 7)), 10, n = 1, target = 340)
#> Error: Partition sampling not available for this case.

## As stated above, the standard multiset case doesn't work either
partitionsSample(0:50, 6, freqs = rep(1:3, 17), n = 2)
#> Error: Partition sampling not available for this case.

## If we use freqs to indicate that zeros can repeat,
## then we can obtain random samples
partitionsSample(0:50, 6, freqs = c(50, rep(1, 50)), n = 3, seed = 222)
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    0    0    1    4    9   36
#> [2,]    0    0    0    0   17   33
#> [3,]    2    4    5    6    8   25

## Even works when the vector is restricted in regards to the target
partitionsSample(0:50, 6, freqs = c(50, rep(1, 50)),
                 n = 3, seed = 222, target = 100)
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    0    1    6   15   29   49
#> [2,]    0    0    0    8   43   49
#> [3,]    4    7   17   19   22   31
```

There is ongoing research in this area and our goal is to eventually be able to cover the standard multiset case.

## `compositionsSample`

The `compositionsSample` function allows one to draw a random sample of compositions of a number. Many of the features present in `comboSample` and `permuteSample` are available in `compositionsSample`.

``` r
## Use the seed parameter to obtain reproducible results
compositionsSample(100, 8, TRUE, n = 3, seed = 42)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    5    4   34   31    7    3    1   15
#> [2,]    3   21    8    6   12   43    6    1
#> [3,]    6    6    1   36   17   18   10    6

## Used namedSample to obtain the lexicographical indices
compositionsSample(100, 8, TRUE, n = 3, seed = 42, namedSample = TRUE)
#>            [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 4024715585    5    4   34   31    7    3    1   15
#> 2756281572    3   21    8    6   12   43    6    1
#> 4873365553    6    6    1   36   17   18   10    6

## Use sampleVec to obtain specific results
compositionsSample(100, 8, TRUE,
                   sampleVec = c(4024715585, 2756281572, 4873365553))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    5    4   34   31    7    3    1   15
#> [2,]    3   21    8    6   12   43    6    1
#> [3,]    6    6    1   36   17   18   10    6

compositionsCount(2500, 10, TRUE)
#> Big Integer ('bigz') :
#> [1] 10324518903611974891453624

## Algorithms are very efficient...
## The below retrieves 10,000 compositions in under a second
system.time(serial <- compositionsSample(2500, 10, TRUE,
                                         n = 1e4, seed = 8128))
#>    user  system elapsed 
#>   0.204   0.001   0.204

## Use nThreads for greater efficiency
system.time(multi <- compositionsSample(2500, 10, TRUE, n = 1e4,
                                        seed = 8128, nThreads = 8))
#>    user  system elapsed 
#>   0.297   0.001   0.044

identical(multi, serial)
#> [1] TRUE

## Sample weak compositions
compositionsSample(0:100, 8, repetition = TRUE, weak = TRUE,
                   seed = 245659, n = 3, namedSample = TRUE)
#>             [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 21547195040   23    0    0    8    5   22   25   17
#> 7649268748     5    0   13   36   42    4    0    0
#> 7598223523     4   54   21    4    6    0    8    3
```

As of version `2.10.0`, we can now unrank compositions with distinct parts as well as the full suite of compositions with repetition (e.g. restricted cases where `target` is specified)

### `compositionSample` with Specific `target`

``` r
compositionsSample(50, 8, TRUE, target = 100, n = 3, seed = 28,
                   namedSample = TRUE)
#>            [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 379550065     1    9    1    2   45   28   11    3
#> 393265634     1    9    9    1    3    4   50   23
#> 8025575563   11   50    8    5    5   10    2    9

compositionsSample(50, 8, TRUE, target = 100,
                   sampleVec = c(379550065, 393265634, 8025575563))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    9    1    2   45   28   11    3
#> [2,]    1    9    9    1    3    4   50   23
#> [3,]   11   50    8    5    5   10    2    9

## Still very fast!
system.time(compositionsSample(1500, 10, TRUE, target = 2500,
                               n = 1e4, seed = 28, nThreads = 8))
#>    user  system elapsed 
#>   1.702   0.005   0.236
```

### `compositionSample` with Distinct Parts

``` r
compositionsSample(50, 8, target = 100, n = 3, seed = 496,
                   namedSample = TRUE)
#>            [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 2965352353   14   16    9    1    3   37    2   18
#> 1410626810    6    7    5   23   10    4   13   32
#> 65651109      1    5   34    7   15   26    4    8

compositionsSample(50, 8, target = 100,
                   sampleVec = c(2965352353, 1410626810, 65651109))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]   14   16    9    1    3   37    2   18
#> [2,]    6    7    5   23   10    4   13   32
#> [3,]    1    5   34    7   15   26    4    8
```

#### Unranking Distinct Parts

The algorithm for unranking compositions with distinct parts is considerably more complex than the corresponding algorithms for standard compositions. While the implementation remains efficient, users should not expect the same level of performance as in the unrestricted case.

``` r
compositionsCount(150, 10, target = 300)
#> Big Integer ('bigz') :
#> [1] 22253682846124800

## Still very fast!
system.time(compositionsSample(150, 10, target = 300, n = 1e3,
                               seed = 496, nThreads = 8))
#>    user  system elapsed 
#>   4.939   0.023   0.653
```

## Sampling Partitions of Groups with `comboGroupsSample`

Just as we can generate random samples of combinations and permutations, we are also able to generate random samples of partitions of groups as well. There are many problems that present in this manner. Below, we examine one involving playing cards.

Let’s say we have 4 players and each player is to have 3 cards a piece. Given that the deck is shuffled, the dealer then distributes 12 cards.

> What possible hands can each player have?

See [Creating A Deck Of Cards In R Without Using While And Double For Loop](<https://stackoverflow.com/a/36903806/4408538>) (Credit to @MichaelChirico)

``` r
cards <- c(2:10, "J", "Q", "K", "A")
suits <- c("♠", "♥", "♦", "♣")
deck <- paste0(rep(cards, length(suits)),  # card values
               rep(suits, each = length(cards))) # suits

set.seed(1738)
shuffled <- factor(deck[sample(52)], levels = deck)

## Here are 2 possibilities
comboGroupsSample(shuffled[1:12], numGroups = 4, n = 2, seed = 13)
#>      Grp1 Grp1 Grp1 Grp2 Grp2 Grp2 Grp3 Grp3 Grp3 Grp4 Grp4 Grp4
#> [1,] 8♦   3♥   5♦   9♦   J♠   7♥   8♠   K♦   10♦  A♦   J♥   3♦  
#> [2,] 8♦   K♦   10♦  9♦   J♥   3♥   J♠   8♠   3♦   A♦   5♦   7♥  
#> 52 Levels: 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠ A♠ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ ... A♣


comboGroupsSample(shuffled[1:12], numGroups = 4, retType = "3Darray",
                  n = 2, seed = 13, namedSample = TRUE)
#> , , Grp1
#> 
#>       [,1] [,2] [,3]
#> 13784 8♦   3♥   5♦  
#> 9152  8♦   K♦   10♦ 
#> 
#> , , Grp2
#> 
#>       [,1] [,2] [,3]
#> 13784 9♦   J♠   7♥  
#> 9152  9♦   J♥   3♥  
#> 
#> , , Grp3
#> 
#>       [,1] [,2] [,3]
#> 13784 8♠   K♦   10♦ 
#> 9152  J♠   8♠   3♦  
#> 
#> , , Grp4
#> 
#>       [,1] [,2] [,3]
#> 13784 A♦   J♥   3♦  
#> 9152  A♦   5♦   7♥  
#> 
#> 52 Levels: 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠ A♠ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ ... A♣
```

What if we add a twist on the problem above. What if instead we want to deal players 1 & 2 two cards, player 3 three cards, and player 4 five cards. How might we do this?

For this, we make use of the `grpSizes` parameter:

``` r
## Again, here are 2 possibilities
comboGroupsSample(shuffled[1:12], grpSizes = c(2, 2, 3, 5),
                  n = 2, seed = 13, namedSample = TRUE)
#>       Grp1 Grp1 Grp2 Grp2 Grp3 Grp3 Grp3 Grp4 Grp4 Grp4 Grp4 Grp4
#> 81667 J♥   10♦  3♦   3♥   8♦   A♦   5♦   9♦   J♠   8♠   K♦   7♥  
#> 71525 K♦   A♦   J♥   5♦   8♦   8♠   3♥   9♦   J♠   3♦   10♦  7♥  
#> 52 Levels: 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠ A♠ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ ... A♣
```

# Ranking

Ranking is the complement of sampling. That is, given a combination (or permutation/partition), determine which lexicographical result it is. As an example, consider all of the combinations of 5 choose 3:

``` r
comboGeneral(5, 3)
#>       [,1] [,2] [,3]
#>  [1,]    1    2    3
#>  [2,]    1    2    4
#>  [3,]    1    2    5
#>  [4,]    1    3    4
#>  [5,]    1    3    5
#>  [6,]    1    4    5
#>  [7,]    2    3    4
#>  [8,]    2    3    5
#>  [9,]    2    4    5
#> [10,]    3    4    5
```

We can see that the rank of the combination: `c(2, 3, 4)` is 7. That is, `c(2, 3, 4)` is the 7<sup>th</sup> combination of 5 choose 3.

## Base R

Just as we saw before, we could easily produce a brute force approach that would work well with small cases, but would become unmanageable very quickly. For example:

``` r
naive_rank <- function(v, m, comb) {
    comb <- as.integer(comb)
    which(apply(combn(v, m), 2, function(x) identical(x, comb)))
}

naive_rank(5, 3, 2:4)
#> [1] 7

## Larger example
comb = comboSample(25, 12, sampleVec = 2e6)[1, ]

system.time(print(naive_rank(25, 12, comb)))
#> [1] 2000000
#>    user  system elapsed 
#>   4.504   0.044   4.550
```

## RcppAlgos Solutions

Similar to the sampling problem, `RcppAlgos` provides four functions: `comboRank`, `permuteRank`, `partitionsRank`, and `compositionsRank` (currently there is not a ranking function for `comboGroups`). These functions are very similar to their sampling counterparts.

For both problems presented above, here is how you would attack them with `comboRank`:

``` r
comboRank(2:4, v = 5)
#> [1] 7

## Since order doesn't matter with combinations, 4:2 should return 7 as well
comboRank(4:2, v = 5)
#> [1] 7

## comb was provided above
system.time(print(comboRank(comb, v = 25)))
#> [1] 2000000
#>    user  system elapsed 
#>       0       0       0
```

All that is needed is the original vector that was used to produce the results and whether or not repetition is used via the `repetition` or `freqs` arguments. The width is determined automatically by the input.

## Rank Multiple Inputs

A neat feature of the ranking functions is the ability to rank multiple inputs at once. We can either pass a single vector, multiple vectors, and we can even pass matrices.

## `comboRank`

``` r
combs = comboSample(50, 8, n = 10, seed = 123, namedSample = TRUE)
combs
#>           [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 161401295    3    4    6   13   40   44   48   50
#> 120710262    2    6   21   29   32   36   42   45
#> 220886245    3   22   23   25   35   36   48   50
#> 442099291   10   11   13   20   21   24   36   45
#> 334689371    6    9   13   20   28   41   43   48
#> 189241370    3    7   18   26   29   31   43   50
#> 168175018    3    4   20   21   27   42   44   49
#> 105740881    2    4   24   27   40   46   48   49
#> 36321127     1    5   10   15   18   32   40   46
#> 292830028    5    8   16   19   34   35   46   47

comboRank(combs, v = 50)
#>  [1] 161401295 120710262 220886245 442099291 334689371 189241370 168175018 105740881
#>  [9]  36321127 292830028
```

## `permuteRank`

``` r
perms_len_5 = permuteSample(100, 5, freqs = rep(1:5, 20),
                            n = 3, seed = 987, namedSample = TRUE)
perms_len_5
#>            [,1] [,2] [,3] [,4] [,5]
#> 3474930553   36   47   93    7   32
#> 5793832271   60   12   27   39   99
#> 797663634     9   16   23    3   35

perms_len_8 = permuteSample(100, 8, freqs = rep(1:5, 20),
                            n = 3, seed = 123, namedSample = TRUE)
perms_len_8
#>                  [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 6897937625624040   73   96   48   62   19   39   60   31
#> 6937176899580966   74   37   42   44   34   80   18   94
#> 5771073522599470   62    7   60   69   14   60    7   30

## Note you can name the inputs
permuteRank(p5 = perms_len_5, p8 = perms_len_8,
            v = 100, freqs = rep(1:5, 20))
#> $p5
#> [1] 3474930553 5793832271  797663634
#> 
#> $p8
#> Big Integer ('bigz') object of length 3:
#> [1] 6897937625624040 6937176899580966 5771073522599470
```

## `partitionsRank`

``` r
parts = partitionsSample(50, 8, target = 100, repetition = TRUE,
                         n = 3, seed = 42, namedSample = TRUE)
parts
#>        [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 61413     1    1    3   11   12   21   23   28
#> 54425     1    1    3    6    7   13   29   40
#> 623844    3    4    4    7    7   15   28   32

partitionsRank(parts, v = 50, target = 100, repetition = TRUE)
#> [1]  61413  54425 623844
```

## `compositionsRank`

``` r
comps = compositionsSample(50, 8, repetition = TRUE,
                           n = 3, seed = 42, namedSample = TRUE)
comps
#>          [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 36761573    4    6    2    1   13    3   15    6
#> 21025945    2   11   13    8    2    3    7    4
#> 71927012   11    4   17    1    2    5    5    5

compositionsRank(comps, v = 50, repetition = TRUE)
#> [1] 36761573 21025945 71927012
```
