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:


*

*The function should be injective (I'm not looking for a hashing function).

*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)$.

*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).
Thank you in advance for your help.
 A: 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.
