An $(n,k)$ deBruijn-Good sequence is a cyclic sequence containing every
$k$-ary $n$-tuple exactly once as a contiguous subsequence.
For example, $$00000100101100111110001101110101$$
is one for $(n,k)=(5,2)$, and
$$000222122021121020120011101$$
is one for $(n,k)=(3,3)$.
A Universal Cycle is a generalization of this idea for other combinatorial
structures, such as $k$-subsets of $[n]$, permutations of $[n]$,
partitions of $[n]$, $k$-dimensional subspaces of a vector space, etc.
For example, $$13567256823472357814782456145712361246783671345834681256$$
lists all $3$-subsets of $[8]$ exacly once.
The biggest open problem here is the \$250 CDG conjecture: for every $k$ and
every large $n$ (maybe only $n\ge k+2$?) for which $n$ divides
$n\choose k$ there is a Ucycle for $k$-subsets of $[n]$.
involves listing all arrays of a certain type within a
larger toroidal array.
The
paper started this area in 1992, and a
was held in Banff in 2004 among an exceptionally fun crew of
Here is a recent
|