Timeline for Indexing schemes of binary sequences
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 14, 2010 at 18:23 | comment | added | Steven Stadnicki | 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. | |
| Jul 14, 2010 at 5:30 | comment | added | falagar | 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. | |
| Jul 14, 2010 at 0:21 | comment | added | Steven Stadnicki | 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$) | |
| Jul 13, 2010 at 23:29 | comment | added | gondolier | 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? | |
| Jul 13, 2010 at 23:08 | history | answered | Steven Stadnicki | CC BY-SA 2.5 |