unrank_combination — Combinations

Generates the combination of \e n objects out of \e m, of the given rank

Interface

#include <codecogs/maths/combinatorics/combinations/unrank_combination.h>

using namespace Maths::Combinatorics::Combinations;

std::vector<int> unrank_combination(int m, int n, int rank)

This function generates the combination of n objects out of m, of the given order. The combinations are considered to be ordered lexicographically, as in the following diagram

$$\begin{array}{rcccccc} 1: & 1, & 2, & \ldots & n - 1, & n \\ 2: & 1, & 2, & \ldots & n - 1, & n + 1 \\ 3: & 1, & 2, & \ldots & n - 1, & n + 2 \\ \ldots \\ m - n + 1: & 1, & 2, & \ldots & n - 1, & m \\ m - n + 2: & 1, & 2, & \ldots & n, & n + 1 \\ m - n + 3: & 1, & 2, & \ldots & n, & n + 2 \\ \ldots \\ last - 2: & m - n, & m - n + 1, & \ldots & m - 1, & m \\ last - 1: & m - n, & m - n + 2, & \ldots & m - 1, & m \\ last: & m - n + 1, & m - n + 2, & \ldots & m - 1, & m \end{array}$$

(1)

where the rank of the last combination is

$$\mathrm{last} = \left( \begin{array}{c} m \cr n \end{array} \right) = \frac{m!}{n!(m - n)!}$$

(2)

References

SUBSET, a C++ library of combinatorial routines, http://www.csit.fsu.edu/~burkardt/cpp_src/subset/subset.html

Example 1

#include <codecogs/maths/combinatorics/combinations/unrank_combination.h>
#include <iostream>
int main()
{
  std::vector<int> comb = Maths::Combinatorics::Combinations::unrank_combination(6, 3, 10);
  std::cout << "Size of the combination: " << comb.size() << std::endl;
  for (int i = 0; i < comb.size(); i++)
    std::cout << comb[i] << "  ";
  std::cout << std::endl;
  return 0;
}

Output:

Size of the combination: 3
1  5  6

Parameters

the size of the base set (choose n out of m elements)

the size of each combination

rank

the lexicographic rank (starting at 1) of the combination to generate

Returns

the combination with the given index