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.
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.
@cite_0
2006913132
The sequence reconstruction problem , first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius @math , where the distance between their centers is at least @math . The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendall-tau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are @math deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.