Optimal encoding of $k$-subsets of $n$ A colleague asks the following question:


  Let $S_k$ denote the subsets of $n$ of size $k$. Is there an optimal
  and efficient encoding of these subsets ? Namely, is there an function
  $f$ from $[0,1]^{\log \binom{n}{k}}$ to $S_k$ that can be computed
  efficiently (ideally in linear time).
This is a question of encoding and decoding constant-weight code. There are several possible efficient algorithms for that, that provide different efficiency benefits.

Here's a list of some papers on this field:

Tenkasi V. Ramabadran. A Coding Scheme for m-out-of-n Codes. IEEE Transactions on Communications, 38(8):1156–1163, August 1990.

Vitaly Skachek, Kees A. Schouhamer Immink: Constant weight codes: An approach based on Knuth's balancing method. ISIT 2011: 321-325

Chao Tian, Vinay A. Vaishampayan, Neil J. A. Sloane: A Coding Algorithm for Constant Weight Vectors: A Geometric Approach Based on Dissections. IEEE Transactions on Information Theory 55(3): 1051-1060 (2009)
and its followup
N. J. A. Sloane, Vinay A. Vaishampayan: Generalizations of Schöbi's Tetrahedral Dissection. Discrete &amp; Computational Geometry 41(2): 232-248 (2009)

All three approaches are/seem to be efficient, but concrete approaches are very different. The first paper uses arithmetic decoding/encoding, the second paper generalizes Knuth's algorithm, and the third paper uses a geometric approach.