unrank combination

viewed 2919 times and licensed 63 times

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

Controller: CodeCogs

Contents

Interface
Unrank Combination
Page Comments

Interface

C++

Unrank Combination

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

Returns

the combination with the given index

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Page Comments

You must login to leave a messge