The Coolest Way to Generate Binary Strings

作者：Stevens Brett; Williams Aaron^*

来源：Theory of Computing Systems, 2014, 54(4): 551-577.

DOI：10.1007/s00224-013-9486-8

• Cool-lex order
• Gray code
• Binary strings
• Combinatorics on words
• Necklace prefix algorithm
• FKM algorithm
• De Bruijn sequence
• Universal cycle
• Hamming distance
• Levenshtein distance

Pick a binary string of length n and remove its first bit b. Now insert b after the first remaining 10, or insert 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, are the binary strings of length n=4, where and . And if you only want strings with weight (number of 1s) between a"" and u? Just insert b instead of when the result would have too many 1s or too few 1s. For example, are the strings with n=4, a""=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) a""=0 and any u (maximum specified weight), (ii) any a"" and u=n (minimum specified weight), and (iii) odd u-a"" (even size weight range). For example, all binary strings with n=6, a""=1, and u=4 appear once (cyclically) in . We also investigate the recursive structure of our order and show that it shares certain sublist properties with lexicographic order.

• 出版日期2014-5