Abstract:
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.
Fulltext:
PDF file (1695 kB)