 français conference home canadam home

Combinatorial Gray codes
Org: Jan Goedgebeur (Ghent University) and Torsten MĂĽtze (TU Berlin)
[PDF]

TORSTEN MĂśTZE, TU Berlin
Trimming and gluing Gray codes  [PDF]

Consider the algorithmic problem of generating each subset of $[n]:=\{1,2,...,n\}$ whose size is in some interval $[a,b]$, $0 \leq a \leq b \leq n$, exactly once by repeatedly adding/removing or exchanging a single element. For $a=0$ and $b=n$ this is the classical problem of generating all $2^n$ subsets of $[n]$ by element additions/removals, and for $a=b$ this is the classical problem of generating all $\binom{n}{a}$ subsets of $[n]$ by element exchanges. We construct efficient algorithms for such Gray codes for a large range of $n$, $a$, and $b$, improving upon several previous results.

Joint work with Petr Gregor (Charles University).

New and simple de Bruijn sequence constructions  [PDF]

New successor-rule based constructions of de Bruijn sequences will be presented. The simple rules are based on the complemented cycling register. To warm up the audience, the talk may begin with a brief survey of known de Bruijn sequence constructions (including Huang's approach).

AARON WILLIAMS, Bard College at Simon's Rock
The Twelvefold Way with Greedy Gray Codes  [PDF]

According to Wikipedia "the twelvefold way is a classification of 12 enumerative problems concerning two finite sets including permutations, combinations, multisets, and partitions of a set or number." For example, the number of ways to put $n$ labelled balls into $n$ unlabeled bins is the $n^{th}$ Bell number.

We show that simple greedy algorithms can generate Gray codes of the associated combinatorial objects. For example, greedily moving the largest possible ball into the bin containing the smallest possible ball creates the Gray code for set partitions originally due to Kaye in 1976.

Joint work with Roop Pal (rpal15@simons-rock.edu).

DENNIS WONG, Northwest Missouri State University
Induced 2-Gray codes inside the Binary Reflected Gray Code  [PDF]

A $2$-BRGC language is a set of binary strings which satisfies two closure properties: (1) Flip the leftmost $1$ produce a string in the set; and (2) Swap the leftmost $1$ with the bit on the right produce a string in the set. Examples of $2$-BRGC languages include binary strings, binary necklaces and prenecklaces, and prefix normal words. We prove that strings in any $2$-BRGC language appear as a cyclic $2$-Gray code when listed in binary reflected Gray code (BRGC) order. We also provide a generic successor rule that computes the next string of a $2$-BRGC language in BRGC order.