Indexing schemes of binary sequences - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T05:33:18Z http://mathoverflow.net/feeds/question/31767 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31767/indexing-schemes-of-binary-sequences Indexing schemes of binary sequences mr.gondolier 2010-07-13T22:04:33Z 2010-07-14T08:57:03Z <p>I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight. </p> <p>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?</p> <p>For example, one could do <em>lexicographical ordering</em>, that is, e.g., $0110 &lt; 1010$. Then this gives the following scheme:</p> <p>$f(x_1^n) = \sum_{k=1}^n x_k \binom{n-k}{w_k}$</p> <p>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?</p> http://mathoverflow.net/questions/31767/indexing-schemes-of-binary-sequences/31775#31775 Answer by Steven Stadnicki for Indexing schemes of binary sequences Steven Stadnicki 2010-07-13T23:08:14Z 2010-07-13T23:08:14Z <p>You want Volume 4, Fascicle 3 of Knuth's <em>The Art of Computer Programming</em>, 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!</p> http://mathoverflow.net/questions/31767/indexing-schemes-of-binary-sequences/31812#31812 Answer by mathy for Indexing schemes of binary sequences mathy 2010-07-14T08:57:03Z 2010-07-14T08:57:03Z <p>You'll probably want to use the <a href="http://en.wikipedia.org/wiki/Combinatorial_number_system" rel="nofollow">combinatorial number system</a> or combinadic. La Wik has a useful overview and a number of references including Knuth's <em>The Art of Computer Programming</em></p>