Much later update
After reading Zodman's comment below and his blog post, it turns out that this can be simplified! As it turns out, it is beneficial to change the setup as follows:
- Start indexing from zero
- Build combinations with zero as the smallest value, i.e. from $0,1,...,n-1$
Then we can answer the following question:
What is the lowest index a combination containing the number $m$?
Since there are $m$ values smaller than $m$, namely $0,1,...,m-1$, there will be:
$$
x=\binom mk
$$
combinations before $m$ appears for the first time. These will have indexes $0,1,...,x-1$ and so the first combination containing $m$ will have index $x$. This leads to both a ranking and an unranking algorithm:
Ranking
This is the name used in the blog post for finding the index given a combination. Consider this worked example:
$$
rank([7,4,0])=\binom 73+\binom 42+\binom 01=35+6+0=41
$$
so the index of the combination $[7,4,0]$ is $41$, since:
- You can make $35$ combinations of three less than $7$, so $[7,1,0]$ has index $35$
- You can make $6$ combinations of two less than $4$, so $[4,0]$ has index $6$ in this set of subcases which is then added, since we are starting from $35$
Formula
$$
rank([c_0,...,c_{k-1}])=\sum_{i=0}^k\binom{c_i}{k-i}
$$
where $c_i$'s are sorted in descending order.
Unranking
This is done similarly, by finding what the blog article calls the combinadic for the index, given $(n,k)$. So if $(n,k)=(10,3)$ and we want to find the $101$-st combination, then we must solve:
$$
101=\sum_{i=0}^k\binom{c_i}{k-i}=\binom 93+\binom62+\binom21=84+15+2
$$
This is solved by being greedy with the larger terms, and we have found $[9,6,2]$ as the answer.
Original answer
Note that the first number only changes after the rest have performed a full set of combinations within the subset they should be in, ie. we have
$$
|\{1xyz\mid 2\leq x<y<z\leq 6\}
$$
making a total of $\binom53=10$ combinations starting with $1$ since the three numbers $x,y$ and $z$ are chosen from the five possible values $2,3,4,5$ and $6$. Similarly we have
$$
|\{2xyz\mid 3\leq x<y<z\leq 6\}
$$
giving us $\binom43=4$ combinations starting with $2$. Based on this principle, we can make a list of values for which the first digit changes:
$$
\begin{array}{|c|c|}
\hline
\text{form}&\text{last }i&\text{formula for last }i\\
\hline
1xyz&10&\binom53=10\\
2xyz&14&10+\binom43=10+4\\
3xyz&15&14+\binom33=14+1\\
\hline
\end{array}
$$
This principle can be repeated down to the next level: Suppose we were to find the $58$-th combination $C=[x,y,z]$ of $k=3$ numbers chosen from $1,2,...,10=n$. Then we see that
$$
\begin{array}{|c|c|}
\hline
x&y&z&\text{last }i&\text{formula for last }i\\
\hline
1&y&z&36&\binom92=36\\
2&y&z&64&36+\binom82=36+28\\
\hline
&3&z&43&36+\binom71=36+7\\
&4&z&49&43+\binom61=43+6\\
&5&z&54&49+\binom51=49+5\\
&6&z&58&54+\binom41=54+4\\
\hline
&&7&55&54+\binom30=54+1\\
&&8&56&55+\binom20=55+1\\
&&9&57&56+\binom10=56+1\\
&&10&58&57+\binom00=57+1\\
\hline
\end{array}
$$
Following the logic of the table above we have $C=[2,6,10]$, and in fact:
$$
58=1+\underbrace{\binom 92}_{\text{1st digit}}+\underbrace{\binom71+\binom61+\binom51}_{\text{2nd digit}}+\underbrace{\binom30+\binom20+\binom10}_{\text{3rd digit}}
$$
where each digit can now be derived from the number of terms $1,3,3$ above as follows:
$$
\begin{align}
x&=1+1&=2\\
y&=x+1+3&=6\\
z&=y+1+3&=10
\end{align}
$$
Here is a Python-code where this is implemented:
def C(n,k): #computes nCk, the number of combinations n choose k
result = 1
for i in range(n):
result*=(i+1)
for i in range(k):
result/=(i+1)
for i in range(n-k):
result/=(i+1)
return result
def cgen(i,n,k):
"""
returns the i-th combination of k numbers chosen from 1,2,...,n
"""
c = []
r = i+0
j = 0
for s in range(1,k+1):
cs = j+1
while r-C(n-cs,k-s)>0:
r -= C(n-cs,k-s)
cs += 1
c.append(cs)
j = cs
return c
Note that this method does never compute previous combinations, but it still has to compute and sum relevant figures for the amount of previous combinations. But it is really fast! For instance, I asked it to compute cgen(173103094564,100,10) which is the $173103094564$-th combination of $k=10$ numbers chosen from $1,2,...,100=n$, and it immediately responded:
[1, 3, 5, 11, 19, 25, 38, 66, 80, 82]
which I would never have guessed, nor have constructed through $173103094564$ iterations!
Just to show the strength of it, I just did
cgen(68814103099439929837637702193841,1000,15)->
[7, 198, 280, 324, 448, 456, 517, 607, 668, 695, 697, 875, 879, 924, 954]
which actually took roughly 3 seconds to compute. We should not complain when we compare this to first having to construct the $68814103099439929837637702193840$ previous combinations - that would be infeasible!
