Fast enumeration of combinatorial objects

B. Ya. Ryabko

Diskretnaya Matematika, Tome 10 (1998) no. 2, pp. 101-119

Résumé

The problem of enumerative encoding is of interest in combinatorics, information theory, and other fields of discrete mathematics. Presently, algorithms to enumerate permutations, combinations, etc., are known, which do not need an exponentially growing amount of memory. The encoding and decoding rates of these methods, which are considered to mean the number of operations on binary words, exceed $c n$, where $c$ is a constant and $n$ is the length of words to be enumerated. We suggest a new enumeration method whose encoding rate is $O(\log^c n)$, $c > 1$.This research was supported by the Russian Foundation for Basic Research, grant 96–01–00052.