# Function mapping combinations to natural numbers

I am looking for a function $f$ mapping combinations (from any finite set) to natural numbers. The hard part is that the function should have the following features:

1. The function should be injective (I'm not looking for a hashing function).
2. Let $g(c_1, c_2)$ be a function that takes two combinations $c_1$ and $c_2$ and returns 1 if $c_1 > c_2$, 0 if $c_1 = c_2$, -1 otherwise according to a certain total order in the set of combinations. If $g(c_1, c_2) = 1$, then $f(c_1) > f(c_2)$ should hold, if $g(c_1, c_2) = 0$ then $f(c_1) = f(c_2)$ and if $g(c_1, c_2) = -1$ then $f(c_1) < f(c_2)$.
3. If $g(c_2, c_1) = 1$ and it doesn't exist any $c$ for which $g(c, c_1) = 1$ and $g(c, c_2) = -1$, then $f(c_2) - f(c_1) = 1$.

I am a computer programmer. I haven't got a strong mathematical background (as you could deduct from my inexact formalism), so I just cannot figure out myself how to build such a function. In order to be more clear, I'll make an example.

$A = \{a_1, a_2, a_3\}$
$C = \{\{a_1, a_2\}, \{a_1, a_3\}, \{a_2, a_3\}\}$
$f(\{a_1, a_2\}) = 0$
$f(\{a_1, a_3\}) = 1$
$f(\{a_2, a_3\}) = 2$

Both the $f(x)$ function and its inverse should be "easy" to compute. The "trivial" solution of creating a reference map by enumerating all the combinations is not an option.

I'm not looking for a ready-to-implement solution that you just provide me - I would create my own function or search for one online and/or in the literature (if I just knew where and how to search).

• What exactly do you mean by "combinations" ? "Couples" or "Permutations" ? – Djaian Apr 3 '13 at 8:59
• I don't mean permutations and I don't limit it to couples. I just mean combinations of $n$ elements of some set. – gd1 Apr 3 '13 at 9:04
• Do you consider $(a_1, a_2)$ and $(a_2, a_1)$ as the same element in $C$ or are they two distincts elements? I mean, is $C$ a set of sets, or a set of vectors? – Djaian Apr 3 '13 at 9:08
• Sorry, my fault (poor formalism). Set of sets. I'll fix the example. – gd1 Apr 3 '13 at 9:09
• No problem, I ask some questions so we can edit your question with a better formalism. Do you accept $\emptyset$ (the empty set) as an element of $C$ ? – Djaian Apr 3 '13 at 9:11

I think what you're looking for is a numbering of the $k$-combinations of a given set. That is, you want a function whose output is equivalent to that of the following. Given a set $A$ of size $n$, and some number $k$,

• Enumerate all subsets of $A$ of size $k$ (there are $\binom{n}{k}$ of them),
• Arrange them in some (any) order,
• Give them numbers from $0$ to $\binom{n}{k} - 1$.

It is possible to efficiently compute such a function, and the most common one is known as "combinatorial number system". The function is as follows:

• Label the elements of $A$ as integers $0$ to $n-1$.
• Given a subset $S$ of $A$ of size $k$, write the elements of the subset in decreasing order, as $S = \{c_k, c_{k-1}, \dots, c_1\}$ with $c_k > \dots > c_1 \ge 0$.
• The function $f(S) = \binom{c_k}k+\cdots+\binom{c_2}2+\binom{c_1}1$.

This is quite fast to compute, and it's also fast to go in the other direction (find the set $S$ given $f(S)$). There is a similar factorial numbering system for numbering permutations.

• Thank you! This is exactly what I am looking for and I'm surprised how wrong where my search queries. I'll read the whole Wikipedia article and figure out how to invert $f$. Thanks again. – gd1 Apr 3 '13 at 9:32
• I've removed $c_0$ from the description; it seemed spurious. – Marc van Leeuwen Apr 3 '13 at 9:33
• @gd1: Inversion is greedy: take $c_k$ as large as possible so that $\binom{c_k}k$ does not exceed your number, then for the remainder do the same with $c_{k-1}$, and so forth. – Marc van Leeuwen Apr 3 '13 at 9:35
• Thank you. Thanks to your suggestions I've managed to write a small Java library to deal with combinations. – gd1 Apr 3 '13 at 21:09