Efficient Computation of Middle Levels Gray Codes

DOI10.1007/978-3-662-48350-3_76MaRDI QIDQ3452851zbMATH OpenOpenAlexFDO

Authors Torsten Mütze, Jerri Nummenpalo

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.07898

zbMATH Keywords

Gray codemiddle levels conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial codes (94B25)

Abstract: For any integer $ngeq1$ a middle levels Gray code is a cyclic listing of all bitstrings of length $2n+1$ that have either $n$ or $n+1$ entries equal to 1 such that any two consecutive bitstrings in the list differ in exactly one bit. The question whether such a Gray code exists for every $ngeq1$ has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. M"utze. Proof of the middle levels conjecture. Proc. London Math. Soc., 112(4):677--713, 2016]. In this work we provide the first efficient algorithm to compute a middle levels Gray code. For a given bitstring, our algorithm computes the next $ell$ bitstrings in the Gray code in time $mathcalO(nell(1+fracnell))$, which is $mathcalO(n)$ on average per bitstring provided that $ell=Omega(n)$.

Recommendations

• Efficient computation of middle levels Gray codes
• A constant-time algorithm for middle levels Gray codes
• A constant-time algorithm for middle levels Gray codes
• Monotone Gray codes and the middle levels problem
• Gray codes, fast Fourier transforms and hypercubes
• On m-ary Gray codes
• Linear time construction of a compressed Gray code
• scientific article; zbMATH DE number 4087600
• Gray codes, loopless algorithm and partitions
• scientific article; zbMATH DE number 4139306

Cites work

• A Survey of Combinatorial Gray Codes
• Adjacent interchange generation of combinations
• An algorithm for generating subsets of fixed size with a strong minimal change property
• An explicit 1-factorization in the middle of the Boolean lattice
• An update on the middle levels problem
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• Construction of 2-factors in the middle layer of the discrete cube
• Efficient Computation of Middle Levels Gray Codes
• Efficient generation of the binary reflected gray code and its applications
• Explicit matchings in the middle levels of the Boolean lattice
• Generation of Permutations by Adjacent Transposition
• Gray codes with restricted density
• scientific article; zbMATH DE number 3838053 (Why is no real title available?)
• Long cycles in the middle two layers of the discrete cube
• Monotone Gray codes and the middle levels problem
• On Rotations and the Generation of Binary Trees
• Proof of the middle levels conjecture
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The Chung-Feller theorem revisited

Cited in

(10)

• Trimming and gluing Gray codes
• A constant-time algorithm for middle levels Gray codes
• Efficient Computation of Middle Levels Gray Codes
• Gray code compression
• Efficient computation of middle levels Gray codes
• A constant-time algorithm for middle levels Gray codes
• Trimming and gluing Gray codes
• Space-optimal quasi-Gray codes with logarithmic read complexity
• On a combinatorial generation problem of Knuth
• A minimum-change version of the Chung-Feller theorem for Dyck paths

This page was built for publication: Efficient Computation of Middle Levels Gray Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452851)