I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.

Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to construct a bijective mapping $f: T_k^n \to \{1, 2, \ldots, \binom{n}{k}\}$ such that computing each $f(x_1^n)$ needs small number of operations?

For example, one could do lexicographical ordering, that is, e.g., $0110 < 1010$. Then this gives the following scheme:

$f(x_1^n) = \sum_{k=1}^n x_k \binom{n-k}{w_k}$

where $w_k=\sum_{i=k}^n x_i$. Suppose computing the binomial coefficients can be done using a look-up table. Then computing each $f(x_1^n)$ needs $\sum_{k=1}^n (k-1) = O(n^2)$ number of operations. Can we do better, say, $O(n)$? Or is it impossible to beat $O(n^2)$?

I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.

Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to construct a bijective mapping $f: T_k^n \to \{1, 2, \ldots, \binom{n}{k}\}$ such that computing each $f(x_1^n)$ needs small number of operations?

For example, one could do lexicographical ordering, that is, e.g., $0110 < 1010$. Then this gives the following scheme:

$f(x_1^n) = \sum_{k=1}^n x_k \binom{n-k}{w_k}$

where $w_k=\sum_{i=k}^n x_i$. Computing $n$ binomial coefficients can be quite demanding. Any other ideas? Or is it impossible to avoid?