text: Abstract We consider the algorithmic problem of generating each subset of [ n ] : = 1 , 2 , … , n whose size is in some interval [ k , l ] , 0 ≤ k ≤ l ≤ n , exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k = 0 and l = n this is the classical problem of generating all 2 n subsets of [ n ] by element additions removals, and for k = l this is the classical problem of generating all ( n k ) subsets of [ n ] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n , k , and l , improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant O ( 1 ) time per generated set and O ( n ) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n -dimensional cube Q n induced by all levels [ k , l ] . We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q 2 k + 1 induced by all levels [ k − c , k + 1 + c ] , c ∈ 0 , 1 , … , k , has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a ( 1 − o ( 1 ) ) -fraction of all vertices.
  @cite_0: Pick a binary string of length n and remove its first bit b. Now insert b after the first remaining 10, or insert @math 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 l and u? Just insert b instead of @math 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, l=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) l=0 and any u (maximum specified weight), (ii) any l and u=n (minimum specified weight), and (iii) odd u?l (even size weight range). For example, all binary strings with n=6, l=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.
summary: In @cite_0 the authors present algorithms for enumerating all vertices of @math for an arbitrary interval @math such that any two consecutive bitstrings have Levenshtein distance at most 2 and Hamming distance at most 4. The Levenshtein distance is the minimum number of bit insertions, deletions, and bitflips necessary to transform one bitstring into another. Again, these enumerations are not cycles in @math and they are not tight. However, the corresponding generation algorithms are loopless, so they are very simple and fast. Improving on this, as a byproduct of the results mentioned in the previous section we obtain a simple loopless algorithm to generate all vertices of @math for an arbitrary interval @math such that any two consecutive bitstrings have Hamming distance and Levenshtein distance at most 2.