A new combinatorial Gray code for balanced combinations

Torsten Mütze

Abstract

(joint work with Christoph Standke and Veit Wiechert)

Efficiently generating all objects in a particular combinatorial class (e.g. subsets, permutations, partitions, strings, trees, triangulations etc.) in such a way that each object is generated exactly once is one of the oldest and most fundamental problems in the area of combinatorial algorithms, and such generation algorithms are used as core building blocks in a wide range of practical applications. In this talk I present a new combinatorial Gray code and a corresponding time- and space-optimal algorithm for generating balanced combinations, i.e., all k-element subsets of {1,2,...,2k}, strengthening the classical Chung-Feller theorem. Balanced combinations are naturally represented by bitstrings of length 2k with exactly k many 1-bits, and thus encode a vast collection of Catalan-type objects such as Dyck paths, ordered trees, binary trees, triangulations