Быстрая нумерация комбинаторных объектов

Проблема нумерационного кодирования представляет интерес для комбинаторики, теории информации и других разделов дискретной математики. В настоящее время известны методы нумерации перестановок, сочетаний и многих других кобинаторных объектов, не использующие экспоненциально растущую память. У этих методов нумерации скорость кодирования и декодирования, измеряемая числом операций над битовыми словами, превосходит $cn$, где $c$ — постоянная, а $n$ — длина нумеруемых слов. В работе предлагается новый метод нумерации, скорость кодирования которого равна $O(\log^cn)$, $c>1$, для перестановок, сочетаний и других комбинаторных объектов, для которых известны методы с неэкспоненциальным объемом памяти.
Работа выполнена при поддержке Pоссийского фонда фундаментальных исследований, грант 96–01–00052.