Abstract
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 sets 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.
Mutze. Proof of the middle levels conjecture.
Proc. London Math.
Soc., 112(4):677-713, 2016]. In a follow-up paper [T.
Mutze and J. Nummenpalo.
An efficient algorithm for computing a middle levels Gray code. ACM Trans.
Algorithms, 14(2):29 pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in timeO(n) on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time O(1) on average, and the required space is O(n).