Middle Levels Gray Codes: Loopless Generation Algorithms and Conjecture
Combinatorial Gray codes involve generating combinatorial objects with minimal differences between consecutive objects. The Middle Levels Conjecture focuses on cyclically generating ground set subsets with specific characteristics. This conjecture has led to significant theoretical and experimental research. Various algorithms have been developed to address this problem, including the exploration of loopless generation algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A constant-time algorithm for middle levels Gray codes Torsten M tze (joint work with Jerri Nummenpalo from ETH Zurich)
Combinatorial Gray codes Problem: Generate all objects in a combinatorial class (permutations, subsets, strings, trees, Dyck paths, etc.) such that consecutive objects differ only a little bit Fundamental task in combinatorial algorithms with many practical applications [Knuth TAOCP Vol. 4A, 11] Ultimate goal: Generate each new object in constant time, [Ehrlich 73] called such algorithms loopless
Combinatorial Gray codes Loopless generation algorithms known for: generating all permutations of by transpositions [Johnson 63], [Trotter 62], [Ehrlich 73], [Dershowitz 75] generating all subsets of by element additions/removals [Gray 53], [Ehrlich 73], [Bitner, Ehrlich, Reingold 76] generating all binary trees with operations [Lucas 87], [Lucas, van Baronaigien, Ruskey 93] vertices by single rotation
The middle levels conjecture Problem: ground set subsets of size , cyclically generate all by element additions/removals or problem is equivalent to generating all bitstrings of length weight or time (weight alternates in each step) Example: {1} {1,2} {2} {2,3} {3} {1,3} with Hamming 100 110 010 011 001 101 , flipping one bit at a total number of generated sets is
The middle levels conjecture Problem: ground set subsets of size Conjecture: Such a Gray code exists for every , cyclically generate all by element additions/removals or . first mentioned in [Havel 83], [Buck, Wiedemann 84] also (mis)attributed to Dejter, Erd s, Trotter and various others appears in the popular books [Winkler, Mathematical puzzles: a connoisseur s collection, 04], [Diaconis, Graham, Magical mathematics, 12] exercise (!!!) in [Knuth TAOCP Vol. 4A, 11] with difficulty rating M49 long line of partial experimental and theoretical results [30+ papers]
The middle levels conjecture Problem: ground set subsets of size Theorem [M. 16 Proc. LMS]: Such a Gray code exists for every Theorem [M., Nummenpalo ESA 15]: There is an algorithm that computes a middle levels Gray code for every with running time on average per generated set. , cyclically generate all by element additions/removals or . Question: Is there a loopless algorithm (running time per generated set)?
Our results Theorem: There is an algorithm that computes a middle levels Gray code for every with running time per generated set. Remarks: initialization time is provided as input to the algorithm, and for a prescribed initial set/bitstring required space is algorithm is optimal for all objectives if the initial set/bitstring is
Our results Theorem: There is an algorithm that computes a middle levels Gray code for every with running time per generated set. Remarks: running time of algorithm described in the paper is on average per generated set can be turned into worst case bound by delaying output values in a buffer of size however, hidden constant in becomes worse time per step steps
Our results Theorem: There is an algorithm that computes a middle levels Gray code for every with running time per generated set. Remarks: implemented algorithm in C++, available for download on http://www.math.tu-berlin.de/~muetze benchmark for 164 days for brute-force search [Shimada, Amano 11] 24 hours reported in [M., Nummenpalo ESA 15] now: 31 minutes ( 8 instructions per generated set) , where :
Our results Theorem: There is an algorithm that computes a middle levels Gray code for every with running time per generated set. Remarks: this yields loopless algorithms also for a number of related Gray codes that have been constructed inductively from the middle levels Gray code [M., Su 15], [Gregor, M. 16]
Proof ideas Gray code = Hamilton cycle in the corresponding graph vertices are the subsets or bitstrings, edges represent element additions/removals or bitflips : Example for : 10110 10101 01101 01011 00111 11100 11010 11001 10011 01110 10001 01100 00110 00101 00011 11000 10100 10010 01010 01001
Proof ideas Gray code = Hamilton cycle in the corresponding graph basic building blocks of the cycle are paths distance between starting vertices same precompute entire bitflip sequence at vertex then flip bits one after the other until vertex (time per step) time on average per generated vertex and is always the i i+1 (time ) i is reached i+1 last bit = 0 last bit = 1 1 2 3
Proof ideas Bitflip rule at vertex can be computed via a lattice path recursion (1-bit = upstep, 0-bit = downstep) corresponding to a Dyck word i bitflip sequence = 16,1,5,2,4,3 ,2,4,1,5, ,7,9,6,10, 15,6,10,7,9,8 ,11,13,10,14,5,15 14,11,13,12 = (111001110011000011000) i
Open problem Our algorithm is optimal with respect to running time and space requirements, but admittedly rather complex Question: Is there a simple loopless algorithm? In particular, is there a simpler proof of the middle levels conjecture?
