Name
Abstract | ||
|---|---|---|
Pick a binary string of length n and remove its first bit b. Now insert b after the first remaining 10, or insert $\overline{b}$ at the end if there is no remaining 10. Do it again. And again. Keep going! Eventually, you will cycle through all 2 n of the binary strings of length n. For example, [InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.] are the binary strings of length n=4, where [InlineEquation not available: see fulltext.] and [InlineEquation not available: see fulltext.]. And if you only want strings with weight (number of 1s) between ℓ and u? Just insert b instead of $\overline{b}$ when the result would have too many 1s or too few 1s. For example, [InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.][InlineEquation not available: see fulltext.] are the strings with n=4, ℓ=0 and u=2. This generalizes `cool-lex' order by Ruskey and Williams (The coolest way to generate combinations, Discrete Mathematics) and we present two applications of our `cooler' order. First, we give a loopless algorithm for generating binary strings with any weight range in which successive strings have Levenshtein distance two. Second, we construct de Bruijn sequences for (i) ℓ=0 and any u (maximum specified weight), (ii) any ℓ and u=n (minimum specified weight), and (iii) odd u驴ℓ (even size weight range). For example, all binary strings with n=6, ℓ=1, and u=4 appear once (cyclically) in [InlineEquation not available: see fulltext.]. We also investigate the recursive structure of our order and show that it shares certain sublist properties with lexicographic order. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00224-013-9486-8 | Theory Comput. Syst. |
Keywords | Field | DocType |
Cool-lex order,Gray code,Binary strings,Combinatorics on words,Necklace prefix algorithm,FKM algorithm,De Bruijn sequence,Universal cycle,Hamming distance,Levenshtein distance | Discrete mathematics,Combinatorics,Loopless algorithm,Binary strings,Gray code,Hamming distance,De Bruijn sequence,Lexicographical order,Combinatorics on words,Mathematics | Journal |
Volume | Issue | ISSN |
54 | 4 | 1432-4350 |
Citations | PageRank | References |
9 | 0.62 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brett Stevens | 1 | 222 | 31.38 |
| Aaron Williams | 2 | 139 | 20.42 |