<p>This is a question of encoding and decoding constant-weight code. There are several possible efficient algorithms for that, that provide different efficiency benefits.</p>

<p>Here's a list of some papers on this field:</p>

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

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

<p>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)</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-08T10:24:12.227Z
2013-10-08T10:24:12.227Z
cryptocat
<p>The "canonical" answer (not necessarily linear time) is to use what could be termed <em>binomial encoding</em> (this is probably the same solution given by Knuth). The idea is to interpret Pascal's identity $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ as stating that the <em>code</em> of those subsets not containing $n$ should fit into $[0,\binom{n-1}{k})$, while the code of those subsets containing $n$ should fit into $[\binom{n-1}{k},\binom{n}{k})$. (The order is arbitrary, of course.)</p>

<p>More precisely, we use the following procedure for encoding:</p>

<p>$\operatorname{ENCODE}(S,n,k)$:</p>

<ol>
<li>If $k = 0$, return $0$.</li>
<li>If $n \notin S$, return $\operatorname{ENCODE}(S,n-1,k)$.</li>
<li>If $n \in S$, return $\binom{n-1}{k}+\operatorname{ENCODE}(S,n-1,k-1)$.</li>
</ol>

<p>You're interested in the inverse function, which decodes a number in $[0,\binom{n}{k})$ into a subset:</p>

<p>$\operatorname{DECODE}(x,n,k)$:</p>

<ol>
<li>If $k = 0$, return $\emptyset$.</li>
<li>If $x &lt; \binom{n-1}{k}$, return $\operatorname{DECODE}(x,n-1,k)$.</li>
<li>If $x \geq \binom{n-1}{k}$, return $\operatorname{DECODE}(x - \binom{n-1}{k},n-1,k-1) \cup \{n\}$.</li>
</ol>

<p>$\operatorname{DECODE}$ can be implemented in linear time if you compute Pascal's table in advance, assuming that subtraction of large numbers has unit cost. The recursion can be easily turned into an iteration, if that makes any difference.</p>

CC BY-SA 3.0
2013-10-09T10:36:30.857Z
Yeah, that's the one Knuth references.
jbapple
CC BY-SA 3.0
2013-10-09T12:08:35.743Z
Well, one of ones.
jbapple
CC BY-SA 3.0
2013-10-09T04:28:26.297Z
2013-10-09T04:28:26.297Z
Yuval Filmus
<p>Well, you could just use a two-way hash map between $S_k$ to $\{0,1\}^{\lceil\lg{{n}\choose{k}}\rceil}$. That's easily computable in each direction in time corresponding to the length of the input, but it uses a lot of space.</p>

<p><a href="http://www-cs-faculty.stanford.edu/~uno/fasc3a.ps.gz" rel="noreferrer">Knuth's "Pre-Fascicle 3a: Generating all combinations"</a>, as well as TaoCP, 7.2.1.3, Theorem L and exercise 17 explore the <a href="https://en.wikipedia.org/wiki/Combinatorial_number_system" rel="noreferrer">"Combinatorial number system"</a>, which is an enumeration of $S_k$ that can be reversed without just computing a huge lookup table. No detailed analysis of run-time is given, but it looks $\omega(\lg{{n}\choose{k}})$ to me.</p>

CC BY-SA 3.0
2013-10-09T01:17:02.183Z
2013-10-09T01:17:02.183Z
jbapple
<p>Isn't $lg{n \choose k} \approx k *lg (n)$?
Naively code each of the set bits by a length $k$ list of their indexes. If you have more than ${n/2}$ encode the zero bits; this takes one extra bit at the front to know which you encoded.  </p>

CC BY-SA 3.0
2013-10-09T17:59:49.023Z
I think that the OP wants a method to "count" all subsets, i.e. given a number in the range $0,\ldots,\binom{n}{k}-1$ (presented in binary notation), come up with an appropriate subset. Also, $\log \binom{n}{k} \approx n\log k - k\log k$ since the subsets are not ordered (comparing $n^{\underline{k}}$ to $\binom{n}{k}$, you lose a factor of $k!$).
Yuval Filmus
CC BY-SA 3.0
2013-10-09T17:17:51.227Z
2013-10-09T17:17:51.227Z
Chad Brewbaker
<p>A colleague asks the following question:</p>

<blockquote>
  <p>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).</p>
</blockquote>

<ds.algorithms><coding-theory>
Optimal encoding of $k$-subsets of $n$
Suresh Venkat
# Optimal encoding of $k$-subsets of $n$

(Asked by: username_0 on 2013-10-08)

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).

**Tags:** ds.algorithms, coding-theory


---

## 4 answers

### Answer by username_1 on 2013-10-08. Score: 8

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 & 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.


---

### Answer by username_2 on 2013-10-09. Score: 8

The "canonical" answer (not necessarily linear time) is to use what could be termed *binomial encoding* (this is probably the same solution given by Knuth). The idea is to interpret Pascal's identity $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ as stating that the *code* of those subsets not containing $n$ should fit into $[0,\binom{n-1}{k})$, while the code of those subsets containing $n$ should fit into $[\binom{n-1}{k},\binom{n}{k})$. (The order is arbitrary, of course.)

More precisely, we use the following procedure for encoding:

$\operatorname{ENCODE}(S,n,k)$:

1. If $k = 0$, return $0$.
2. If $n \notin S$, return $\operatorname{ENCODE}(S,n-1,k)$.
3. If $n \in S$, return $\binom{n-1}{k}+\operatorname{ENCODE}(S,n-1,k-1)$.

You're interested in the inverse function, which decodes a number in $[0,\binom{n}{k})$ into a subset:

$\operatorname{DECODE}(x,n,k)$:

1. If $k = 0$, return $\emptyset$.
2. If $x < \binom{n-1}{k}$, return $\operatorname{DECODE}(x,n-1,k)$.
3. If $x \geq \binom{n-1}{k}$, return $\operatorname{DECODE}(x - \binom{n-1}{k},n-1,k-1) \cup \{n\}$.

$\operatorname{DECODE}$ can be implemented in linear time if you compute Pascal's table in advance, assuming that subtraction of large numbers has unit cost. The recursion can be easily turned into an iteration, if that makes any difference.

> **Comments:**
> **username_3**: Yeah, that's the one Knuth references.  
> **username_3**: Well, one of ones.  

---

### Answer by username_3 on 2013-10-09. Score: 5

Well, you could just use a two-way hash map between $S\_k$ to $\{0,1\}^{\lceil\lg{{n}\choose{k}}\rceil}$. That's easily computable in each direction in time corresponding to the length of the input, but it uses a lot of space.

[Knuth's "Pre-Fascicle 3a: Generating all combinations"](http://www-cs-faculty.stanford.edu/~uno/fasc3a.ps.gz), as well as TaoCP, 7.2.1.3, Theorem L and exercise 17 explore the ["Combinatorial number system"](https://en.wikipedia.org/wiki/Combinatorial_number_system), which is an enumeration of $S\_k$ that can be reversed without just computing a huge lookup table. No detailed analysis of run-time is given, but it looks $\omega(\lg{{n}\choose{k}})$ to me.


---

### Answer by username_4 on 2013-10-09. Score: 2

Isn't $lg{n \choose k} \approx k \*lg (n)$?
Naively code each of the set bits by a length $k$ list of their indexes. If you have more than ${n/2}$ encode the zero bits; this takes one extra bit at the front to know which you encoded.

> **Comments:**
> **username_2**: I think that the OP wants a method to "count" all subsets, i.e. given a number in the range $0,\ldots,\binom{n}{k}-1$ (presented in binary notation), come up with an appropriate subset. Also, $\log \binom{n}{k} \approx n\log k - k\log k$ since the subsets are not ordered (comparing $n^{\underline{k}}$ to $\binom{n}{k}$, you lose a factor of $k!$).  

---

