The Coolest Way to Generate Binary Strings

作     者：Stevens, Brett Williams, Aaron 

作者机构：Carleton Univ Sch Math & Stat Ottawa ON K1S 5B6 Canada McGill Univ Dept Math & Stat Montreal PQ Canada 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2014年第54卷第4期

页      面：551-577页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：NSERC ONR 

主　　题：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.