## Indexing schemes of binary sequences

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

## 2 Answers

You want Volume 4, Fascicle 3 of Knuth's The Art of Computer Programming, chapter 7.2.1.3: "Generating All Combinations" - I won't include links because everyone has a favorite online bookseller, but AFAIK all the major ones have it in stock. Highly, highly recommended!

-

thanks. will take a look! i heard before that this enumeration problem needs at least $O(n^2)$ binary operations. The above lexicographic enumeration needs to be computed using $n$ operations on a $n$-bit register, which is $O(n^2)$. Does DEK talk about this? – mr.gondolier Jul 13 2010 at 23:29
I think there was some discussion about the complexity of generation, but I'm not sure if your specific issue was discussed - I'll check when I get home.  Also, even if you have $O(n^2)$ worst-case performance, keep in mind that amortized performance may be much better (think of enumerating the numbers from $1$ to $2^n$ in a single register - you may have to change up to $n$ bits on any given operation, but the total number of bits changed is still just $2^{(n+1)}$, not $n2^n$) – Steven Stadnicki Jul 14 2010 at 0:21
If you need frequently compute number of sequence you can pre-calculate all $\binom{i}{j}$. This would make you algorithm run in $O(n)$ time and $O(nk)$ memory. – falagar Jul 14 2010 at 5:30
I had some chance to look at this last night - Knuth's primary focus is on iteration, not on generating the indexing you mention, but he has a number of schemes that can iterate over all combinations with very few bit operations per iteration; if you don't explicitly need indices (and my gut instinct is that you're unlikely to), then his algorithms very definitely bear looking into. – Steven Stadnicki Jul 14 2010 at 18:23

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

You'll probably want to use the combinatorial number system or combinadic. La Wik has a useful overview and a number of references including Knuth's The Art of Computer Programming

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9387953281402588, "perplexity_flag": "middle"}