A constant-time algorithm for middle levels Gray codes

For any integer n ≥ 1 a middle levels Gray code is a cyclic listing of all n -element and ( n + 1)- element subsets of {1, 2, …, 2n +1} such that any two consecutive subsets differ in adding or removing a single element. The question whether such a Gray code exists for any n ≥ 1 has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. To appear in Proc. London Math. Soc. , 2014]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. Proc. ESA, 2015] this existence proof was turned into an algorithm that computes each new set in the Gray code in time O ( n ) on average. In this work we complete this line of research by presenting an algorithm for computing a middle levels Gray code in optimal time and space: Each new set is generated in time O (1), and the required space is O ( n ).

Authors

• Torsten Mütze
• Jerri Nummenpalo

Keywords

No keywords are indexed for this paper.