5
$\begingroup$

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

Thank you in advance for your help.

$\endgroup$
  • $\begingroup$ What exactly do you mean by "combinations" ? "Couples" or "Permutations" ? $\endgroup$ – Djaian Apr 3 '13 at 8:59
  • $\begingroup$ I don't mean permutations and I don't limit it to couples. I just mean combinations of $n$ elements of some set. $\endgroup$ – gd1 Apr 3 '13 at 9:04
  • $\begingroup$ 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? $\endgroup$ – Djaian Apr 3 '13 at 9:08
  • $\begingroup$ Sorry, my fault (poor formalism). Set of sets. I'll fix the example. $\endgroup$ – gd1 Apr 3 '13 at 9:09
  • $\begingroup$ 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$ ? $\endgroup$ – Djaian Apr 3 '13 at 9:11
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gd1 Apr 3 '13 at 9:32
  • $\begingroup$ I've removed $c_0$ from the description; it seemed spurious. $\endgroup$ – Marc van Leeuwen Apr 3 '13 at 9:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Apr 3 '13 at 9:35
  • $\begingroup$ Thank you. Thanks to your suggestions I've managed to write a small Java library to deal with combinations. $\endgroup$ – gd1 Apr 3 '13 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.