Fast way to get a position of combination (without repetitions) This question has an inverse: (Fast way to) Get a combination given its position in (reverse-)lexicographic order

What would be the most efficient way to translate a combination of $k$-tuple into its positions within the $\left(\!\!\binom{n}{k}\!\!\right)$ combinations?
I need this to be fast for combinations of $\left(\!\!\binom{70}{7}\!\!\right)$ order of magnitude - very large, but not exceeding 2 billion (fits into int32 maximum value).
Below is an example of $\left(\!\!\binom{6}{3}\!\!\right)$, where the aim is to quickly translate (a, d, f) tuple to value 9, while in the real problem $k$ ranges between 5 and 8.
$$\begin{array}
{cccccc|c}
a&b&c&d&e&f&^{combination}/_{sort\_order}&
\\\hline
x&x&x& & & &1\\
x&x& &x& & &2\\
x&x& & &x& &3\\
x&x& & & &x&4\\
x& &x&x& & &5\\
x& &x& &x& &6\\
x& &x& & &x&7\\
x& & &x&x& &8\\
x& & &x& &x&9\\
x& & & &x&x&10\\
.&.&.&.&.&.&.\\
 & & &x&x&x&20\\
\end{array}$$
I know that I could pre-calculate all the combinations and reverse the lookup dictionary. However, such dictionary would not be efficient in terms of memory usage. Therefore I am looking for either calculation-based approach, or a more efficient data structure to perform this mapping.
 A: Let us denote your tuple [a b c] as [1 1 1 0 0 0] and so on.
Define $\binom{n}{r}=0$ for $n<r$
For your tuple: $[a d f] = [1 0 0 1 0 1]$
$$P = 1\cdot \binom{0}{1}+0\cdot \binom{1}{1}+0\cdot \binom{2}{1}+1\cdot \binom{3}{2}+0\cdot\binom{4}{2}+1\cdot\binom{5}{3} + 1$$
$$P=0 + 0 +0 +3+0+10+0+1 = 14$$
General Algorithm: 


*

*Calculate the position value of each binary digit using $\binom{n}{r}$

*Take $n$ as position of the digit from left, for leftmost digit $n=0$.

*Write $r$ for each position as the number of 'ONES' counted from left, including the one at current position. 


Example-1: [a b c] = [1 1 1 0 0 0]
Calculate the position of the tuple as sum:
$$P = 1\cdot \binom{0}{1}+1\cdot \binom{1}{2}+1\cdot \binom{2}{3}+0\cdot \binom{3}{3}+0\cdot\binom{4}{3}+0\cdot\binom{5}{3} + 1$$
$$P=0 + 0 +0 +0+0+0+0+1 = 1$$
Example-2: [d e f] = [0 0 0 1 1 1]
$$P = 0\cdot \binom{0}{0}+0\cdot \binom{1}{0}+0\cdot \binom{2}{0}+1\cdot \binom{3}{1}+1\cdot\binom{4}{2}+1\cdot\binom{5}{3} + 1$$
$$S=0+0+0+3+6+10+1=20$$
The lone ONE is added because you are not starting at zero. 
A: I'll relabel your (a,d,f) to (1,4,6) and denote it by $(i_1,i_2,i_3)$ so we can calculate with it. 
Start at index $\binom nk$. Moving the $k$-th entry to the left by $1$ reduces the index by $1=\binom{n-j}0$. Moving the $(k-1)$-th entry to the left from $j$ to $j-1$ reduces the index by $n-j=\binom{n-j}1$. Generally, moving the $(k-m)$-th entry to the left from $j$ to $j-1$ reduces the index by $\binom{n-j}m$. Thus the index is
$$
\binom nk-\sum_{m=0}^{k-1}\;\sum_{j=i_{k-m}+1}^{n-m}\binom{n-j}m\;.
$$
You can easily precalculate the inner sums so that you can look them up using $m$ and $i_{k-m}$, so you just need to add up the $k$ terms in the sum over $m$ to get the index.
P.S.: That was unnecessarily complicated; the inner sum simplifies, and the result is
$$
\binom nk-\sum_{m=0}^{k-1}\binom{n-i_{k-m}}{m+1}\;.
$$
You can probably derive that more directly, but since you're perhaps just interested in a practical result and not the most elegant way of deriving it, I'll leave it at that.
A: Your tuple ordering is lexicographic and your to-be-computed position
is one-based, as are the symbol codes for $a,b,\ldots$ used in @joriki's answer;
but for the sake of simplicity I will use reverse-lexicographic ordering
and zero-based positions and letter codes.
Conversion is done by replacing @joriki's $(i_1,\ldots,i_k)$
with $(n-i_k,\ldots,n-i_1)$
and replacing the position resulting from my formula with its distance to
$\binom{n}{k}$.
The result below is thus consistent with @joriki's formula.
I have used such computations for compression of multi-indices
into (skew-)symmetric tensors; therefore I borrow some vocabulary from that
domain.
Let us define a $k$-index to be
a $k$-tuple of strictly increasing nonnegative integers.
You may have to sort accordingly and to disallow duplicate entries.
$k$-indices can be totally ordered in a reverse-lexicographic manner:
Sorting is done by the last element,
in case of equality by the next-to-last element, and so on.
For a $k$-index $I$, let us define its position (or compressed index)
$\operatorname{ordx}(I)$ as the number of $k$-indices
that are reverse-lexicographically smaller than $I$.
Note that $\operatorname{ordx}(I) = 0$
for the smallest $k$-index $I=(0,\ldots,k-1)$.
We need a notation for truncated tuples.
Denoting $I = (i_0,\ldots,i_{k-1})$,
let $I_m = (i_0,\ldots,i_{k-m-1})$ for integer $m$ with $0\leq m<k$.
That is $I$ with the last $m$ elements chopped off.
Now a $k$-index $J=(j_0,\ldots,j_{k-1})$ is
reverse-lexicographically smaller than $I$ if and only if


*

*$j_{k-1} < i_{k-1}$;
there are $\binom{i_{k-1}}{k}$ such $k$-indices; or

*$k>1$, and $j_{k-1} = i_{k-1}$,
and $J_1$ is reverse-lexicographically smaller than $I_1$.
This condition involves a comparison of $(k-1)$-indices.


Proceeding by induction, we arrive at the formula
$$\operatorname{ordx}(I) = \sum_{r=1}^k\binom{i_{r-1}}{r}$$
It is worth noting that this formula does not depend on the upper bound $n$
for the index elements.
The binomial coefficient values can be computed on the fly
by initializing and updating a segment of Pascal's triangle.
Define
$$b_{j}^{(r)} = \binom{j+r}{r} = \begin{cases}
1 & \text{if $r=0$ or $j=0$} \\
b_{j}^{(r-1)} + b_{j-1}^{(r)} & \text{if $r>0$ and $j>0$}
\end{cases}$$
So we just need to initialize and update an array
$$B^{(r)} = \left(b_0^{(r)},\ldots,b_{i_{k-1}-k}^{(r)}\right)$$
In practice, we prepend a $0$ to that array in order to account
for the case $i_{r-1} = r-1$ which requires a zero binomial coefficient.
In Python (which uses zero-based indices and half-open ranges):
def ordx(idx):
    """
    Turns a multi-index of strictly increasing nonnegative integers
    into a 1-dimensional zero-based index.
    """
    s = 0
    b = [0] + [1] * (idx[-1] + 1 - len(idx))    # [0, 1, 1, ...]
    for r,i in enumerate(idx):      # (0,idx[0]), (1,idx[1]), ...
        for j in xrange(2, len(b)): # 2, ..., len(b)-1
            b[j] += b[j-1]          # binomial(j+r, r+1)
        s += b[i - r]
    return s

Besides:
If you want to allow duplicate tuple elements, you can transform that
problem by adding to each element $i_r$ the sub-index $r$ and
computing ordx for the modified tuple which now has strict increments.
For that use case, the code above gets simplified a bit:
def ords(idx):
    """
    Turns a multi-index of nondecreasing nonnegative integers
    into a 1-dimensional zero-based index.
    """
    s = 0
    b = [0] + [1] * idx[-1]         # [0, 1, 1, ..., 1]
    for i in idx:
        for j in xrange(2, len(b)): # 2, ..., len(b)-1 = idx[-1]
            b[j] += b[j-1]
        s += b[i]
    return s

This computes
$$\operatorname{ords}(I) = \sum_{r=0}^{k-1}\binom{i_r + r}{r+1}$$
Such a function ords could be used for compressing a sorted multi-index
for totally symmetric tensors to a flat index that removes redundancy.
Update:
The above algorithms are simple, but need to update an array of binomial
coefficients for each index element.
Consequently, running the above ords needs $k\,i_{k-1}$ additions
and an array b of length $i_{k-1}+1$.
For ordx replace $i_{k-1}$ with $i_{k-1}-k+1$.
We can reduce the operation count and memory usage by computing
each needed binomial coefficient directly from the previous one.
This requires a sequence of multiplications and divisions instead
of just additions, but it reduces binomial bookkeeping to one scalar variable
and keeps total ords operation count at $\operatorname{O}(k+i_{k-1})$.
Correspondingly, ordx operation count is $\operatorname{O}(i_{k-1})$.
Here is a sample Python implementation of the optimized $\operatorname{ordx}$
(with // denoting integer division):
def ordx_opt(idx):
    """
    Turns a multi-index of strictly increasing nonnegative integers
    into a 1-dimensional zero-based index.
    """
    s = 0
    j = 1
    b = 1
    for r,i in enumerate(idx):  # (0,idx[0]), (1,idx[1]), ...
        if i == r: continue     # skipping terms with zero binomial coeff
        # b == binomial(j+r-1, r), update to j == i - r
        while j < i - r:
            b *= j + r
            b //= j
            j += 1
        # b == binomial(i-1, r), update to binomial(i, r+1)
        b *= i
        b //= r + 1
        s += b
    return s

And the corresponding optimized $\operatorname{ords}$:
def ords_opt(idx):
    """
    Turns a multi-index of nondecreasing nonnegative integers
    into a 1-dimensional zero-based index.
    """
    s = 0
    j = 1
    b = 1
    for r,i in enumerate(idx):
        if i == 0: continue     # skipping terms with zero binomial coeff
        # b == binomial(j+r-1, r), update to j == i
        while j < i:
            b *= j + r
            b //= j
            j += 1
        # b == binomial(i+r-1, r), update to binomial(i+r, r+1)
        b *= i + r
        b //= r + 1
        s += b
    return s

A: I posted the same question and was pointed here.  I was able to use joriki's solution, slightly tweaked, and came up with the following C# code:
public int GetCombID(List<int> comb, int max = 51)
{
    UInt64 id = nCr(max + 1, comb.Count);            
    for (int i = 0; i < comb.Count; i++)
        id -= nCr(max - comb[i], comb.Count - i);
    return (int)id;
}

To reverse the process I use the following:
public List<int> GetCombFromID(int id, int combLength = 2,  int max = 51)
{
    List<int> comb = new List<int>(combLength);
    var tId = nCr(max + 1, combLength) - (UInt64)id;
    for(int i = combLength; i > 0; i--)
    {
        UInt64 tVal = 0;
        bool done = false;
        int pos = 0;
        while(!done)
        {
            var t = nCr(max - pos, i);
            if (t <= tId)
            {
                tVal = t;
                done = true;
            }
            pos++;
        }
        tId -= tVal;
        comb.Add(pos - 1);
    }

    return comb;
}

I post this now as a reference for others in the future.
