On a combinatorial generation problem of Knuth

DOI10.1137/20M1377394MaRDI QIDQ5080484zbMATHOpenAlexFDO

Authors Arturo I. Merino, Ondřej Mička, Torsten Mütze

Publication date 31 May 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclegray codemiddle levels conjecture

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Abstract: The well-known middle levels conjecture asserts that for every integer $ngeq1$, all binary strings of length $2(n+1)$ with exactly $n+1$ many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position. In his book `The Art of Computer Programming Vol. 4A' Knuth raised a stronger form of this conjecture (Problem 56 in Chapter 7, Section 2.1.3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has $2n+1$ blocks of the same length, and each block is obtained by adding $s=1$ (modulo $2n+1$) to the previous block. In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts $sgeq1$ that are coprime to $2n+1$. We also present an algorithm to compute this ordering, generating each new bitstring in $mathcalO(n)$ time, using $mathcalO(n)$ memory in total.

Recommendations

• Proof of the middle levels conjecture
• Efficient computation of middle levels Gray codes
• Efficient Computation of Middle Levels Gray Codes
• Trimming and gluing Gray codes
• Trimming and gluing Gray codes

Cites work

• scientific article; zbMATH DE number 3838053 (Why is no real title available?)
• scientific article; zbMATH DE number 3535592 (Why is no real title available?)
• scientific article; zbMATH DE number 3568702 (Why is no real title available?)
• scientific article; zbMATH DE number 3628955 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2050057 (Why is no real title available?)
• scientific article; zbMATH DE number 6850346 (Why is no real title available?)
• scientific article; zbMATH DE number 3801574 (Why is no real title available?)
• scientific article; zbMATH DE number 822743 (Why is no real title available?)
• scientific article; zbMATH DE number 4195954 (Why is no real title available?)
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• A constant-time algorithm for middle levels Gray codes
• A short proof of the middle levels theorem
• 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
• Distance-2 Cyclic Chaining of Constant-Weight Codes
• Doubly adjacent gray codes for the symmetric group
• Efficient generation of the binary reflected gray code and its applications
• Explicit matchings in the middle levels of the Boolean lattice
• Gray codes with restricted density
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Hamilton cycles and paths in vertex-transitive graphs-current directions
• Hamiltonian paths in Cayley graphs
• Lexicographic matchings cannot form Hamiltonian cycles
• Lexicographically least circular substrings
• Long cycles in the middle two layers of the discrete cube
• Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner
• Monotone Gray codes and the middle levels problem
• On generalized middle-level problem
• Perfect Snake-in-the-Box Codes for Rank Modulation
• Probabilistic combinatorics and the recent work of Peter Keevash
• Proof of the middle levels conjecture
• Shorthand universal cycles for permutations
• Some Hamilton Paths and a Minimal Change Algorithm
• Some properties of a centroid of a free tree
• Sparse Kneser graphs are Hamiltonian
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The coolest way to generate combinations
• The prism over the middle-levels graph is Hamiltonian

Cited in

(3)

• On \(O(1)\) time algorithms for combinatorial generation
• An alternate form of Merino-Mička-Mütze's solution to a Knuth's combinatorial generation problem.
• On the hardness of Gray code problems for combinatorial objects

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On a combinatorial generation problem of Knuth

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