A constant-time algorithm for middle levels Gray codes
Torsten Mütze, Jerri Nummenpalo · 2017
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).