Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

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!

share|improve this answer
    
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 '10 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 '10 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 '10 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 '10 at 18:23
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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