6
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah, that's the one Knuth references. $\endgroup$ – jbapple Oct 9 '13 at 10:36
  • 2
    $\begingroup$ Well, one of ones. $\endgroup$ – jbapple Oct 9 '13 at 12:08
4
$\begingroup$

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", as well as TaoCP, 7.2.1.3, Theorem L and exercise 17 explore the "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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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!$). $\endgroup$ – Yuval Filmus Oct 9 '13 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.