The Coolest Order of Binary Strings

摘要

Pick a binary string of length n and remove its first bit b. Now insert 6 after the first remaining 10, or insert 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, (■□) are the binary strings of length n = 4, where 1 = □ and 0 = ■. Che bello! And if you only want strings with weight (number of 1s) between ℓ and u? Just insert b instead of b when the result would have too many 1s or too few 1s. For example, (■□) are the strings with n = 4, ℓ = 0 and u = 2. Strabello! This generalizes 'cool-lex' order by Ruskey and Williams (The coolest way to generate combinations, Discrete Mathematics). We use it to 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 (■□).