Русский
!

Conference publications

Abstracts

XXII conference

Generation algorithms of the partitions class of natural number

Perminova M.Y., Kruchinin V.V.

Tomsk State University of Control Systems and Radioelectronics, Russia

1 pp. (accepted)

Алгоритмы комбинаторной генерации разбиений натуральных чисел имеют важное научное и практическое значение. Так при вычислениях формулы Фа Ди Бруно и симметрических полиномов используются алгоритмы генерации разбиений. Известна связь между разбиениями и композициями натурального числа, что также приводит к необходимости генерировать разбиения. При построении многих классов деревьев на основе процедуры полного разбиения также используются алгоритмы генерации разбиений. Уже получены и исследованы алгоритмы комбинаторной генерации всех разбиений и разбиений, имеющих $m$ позиций. Однако алгоритмы комбинаторной генерации ограниченных разбиений авторам не известны.

Рассмотрим алгоритмы комбинаторной генерации одного класса ограниченных разбиений. Этот класс разбиений исследовал Дж. Эндрюс. В своей работе~\cite{Andrus} он получил рекуррентную формулу $p(N,M,n)$ --- числа разбиений $n$ не более чем на $M$ частей, каждая из которых не превосходит $N$: $$p(N,M,n)=p(N,M-1,n)+p(N-1,M,n-M).$$

В основе метода построения алгоритмов комбинаторной генерации ограниченных разбиений лежит построение дерева решений (частный случай И/ИЛИ дерева). Используя метод построения алгоритмов комбинаторной генерации, получены алгоритмы последовательной генерации, генерации по номеру и алгоритм нумерации для рассмотренного класса разбиений.

Анализ показал, что алгоритм последовательной генерации хуже уже известного алгоритма Кнута~\cite{Knuth}. Однако достоинством данного алгоритма является тот факт, что он использует дерево разбиений. Это означает, что алгоритм последовательной генерации можно использовать совместно с алгоритмами нумерации и генерации по номеру. Например, если нам необходимо генерировать не все множество разбиений, а некоторое подмножество. С помощью модификации алгоритма генерации разбиения по номеру первоначально создаем стек с заданным следом дерева и далее запускаем алгоритм последовательной генерации. В этом случае сложно воспользоваться алгоритмом Кнута, поскольку в нем используется механизм перестановок.

\begin{thebibliography}{100}

\bibitem{Andrus} \textit{Эндрюс Г.} Теория разбиений / пер. с англ. --- М.: Наука. Главная редакция физико-математической литературы, 1982. --- 256 с.

\bibitem{Knuth} \textit{Кнут Д.} Искусство программирования, том 4, выпуск 3: генерация всех сочетаний и разбиений : пер. с англ. --- М. : ООО <<И.Д. Вильямс>>, 2007. --- 208 с.

\end{thebibliography}



© 2004 Designed by Lyceum of Informational Technologies №1533