0

I'm looking for a bijective mapping which maps an n-tuple onto/into a subset {1, 2, 3, ..., nCr) of Z where the n-tuples are (non-repeating) combinations of the integers {0, 1, 2, ..., r - 1}.

For example, (1, 5, 10) maps to x where (1, 5, 10) is an ordered triple representation of a combination of {0, 1, 2, ..., 14} and thus 1 <= x <= 15C3.

For our purposes, assume the elements of the tuple are zero based but the result is 1 based. Also, assume the elements of the tuple are in ascending order.

I need the solution to either be a formula or an algorithm and not just "calculate all possible combinations in an orderly way and number them".

This is somewhat like Lehmer encoding but I need it for combinations rather than permutations. Does anyone know a solution to this?

Edit: Though none of the solutions in the linked question are marked as the solution, I was able to use (with a slight tweak) joriki's solution for my purposes. Thanks guys!

nurdyguy
  • 141
  • So, let me confirm, you are asking for an explicit bijection between $[\binom{n}{r}]={0,1,2,\dots,\binom{n}{r}-1}$ and $\binom{[n]}{r}={A~:~A\subseteq{0,1,2,\dots,n-1},~|A|=r}$? – JMoravitz Dec 19 '16 at 21:30
  • Sorry, I'm terrible at writing here using correct Mathematical notation. If S is the set of all possible combinations r chosen from n, F: S <=> {1, 2, .., nCr}. Basically I want to take each possible combination and give it an "ID" value which can be calculated or inverted. – nurdyguy Dec 19 '16 at 21:36
  • Thanks @ccorn. I'll dig in a bit deeper and see if that works for me. – nurdyguy Dec 19 '16 at 21:54

1 Answers1

0

Written from the perspective of going from the subsets of $\{1,2,\dots,n\}$ of size $r$ to the set $\{1,2,3,\dots,\binom{n}{r}$}

Suppose we have the input $\{a_1,a_2,\dots,a_r\}$ with $a_1\leq a_2\leq\dots$

We wish to count how many subsets are "smaller" than it in regards to a lexicographic ordering. To do so, we first look to the smallest number in the set and try to count how many subsets have a smaller first number. There are $\binom{n}{r}-\binom{n-a_1+1}{r}$ sets whose smallest element is less than $a_1$.

We continue, trying to find how many subsets which begin with $a_1$ but have a smaller second number. As there are $\binom{n-a_1}{r-1}$ subsets of size $r$ whose smallest number is $a_1$ and $\binom{n-a_2+1}{r-1}$ of these have second number greater than or equal to $a_2$, there are $\binom{n-a_1}{r-1}-\binom{n-a_2+1}{r-1}$ sets smaller in this case.

Continuing in this fashion, we eventually add up the number of subsets "smaller" than it by having calculated the amounts in each of these cases:

  • Those sets who have a smaller first element
  • Those sets who have the same first element but smaller second element
  • Those sets who have the same first and second element but smaller third element
  • $\vdots$
  • Those sets who have the same first $k$ elements but smaller $k+1$'st element
  • $\vdots$
  • Those sets who have the same first $r-1$ elements but smaller $r$'th element

Adding all of these values together will give how many elements are less than it, so adding one will give which position it is in line.

The position in line will be $1+\sum\limits_{k=0}^r\left(\binom{n-a_k}{r-k}-\binom{n-a_{k+1}+1}{r-k}\right)$ letting $a_0=0$ and $a_{r+1}=n+1$

E.g. $\color{red}{\{1,3,5\}}$'s position in the lexicographic ordering of the subsets of $\{1,2,\dots,6\}$ should be:

$\binom{6}{3}-\binom{6}{3}+\binom{5}{2}-\binom{4}{2}+\binom{3}{1}-\binom{2}{1}+1=6$

As an additional example, $\{1,5,6\}$ would have position

$\binom{6}{3}-\binom{6}{3}+\binom{5}{2}-\binom{2}{2}+\binom{1}{1}-\binom{1}{1}+1=10$

Indeed, the twenty subsets of $\{1,2,\dots,6\}$ of size three are in order:

$\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,2,6\},\{1,3,4\},\color{red}{\{1,3,5\}},\{1,3,6\},\{1,4,5\},\{1,4,6\},\color{blue}{\{1,5,6\}},\{2,3,4\},\dots$

and they do indeed appear as the sixth and tenth entries on the list

JMoravitz
  • 79,518