Київський Вісник Київського національного університету імені Тараса Шевченка / Київський, університет імені національний; редкол.: голов. ред. Анісімов А.В. ; Хусаінов Д.Я., Arturs Medvids, Miklos Ronto [та ін.]. - Київ, 2016
Анотація:
В статті розглядаються методи нумерації розбиттів скінченних множин. Запропоновані алгоритми дозволяють обчислювати номер (індекс) розбиття та будувати розбиття скінченної множини за його номером (індексом). Для одного з методів показано, як будується дерево пошуку, яке хоча і не є рівноважним, але має високу швидкість спуску. Наведені методи дають також можливість будувати наступне розбиття множини для заданого розбиття, якщо, звісно, задане розбиття не є останнім за номером (індексом), що важливо длявипадку генерації усіх розбиттів даної скінченної множини. Аналогічно можна обчислювати попереднє розбиття для заданого розбиття. Усі методи наведені з детальними алгоритмами та посиланнями на код відповідних програм, які викладені у мережі Інтернет.
Here we consider ways of set partitions numbering and obtaining the index of specific set partition or finding a set partition by its index. One of these methods is shown to have a search tree that is not an equilibrium one though it has rather good speedof descent due to the appropriate algorithm. These approaches make it possible to build next set partition for the current set partition if the current set partition is not the last one. This feature is rather useful if one needs just to generate all& possible partitions for a given finite set. Similarly, one can easily obtain the previous set partition for the current set partition if the current set partition is not the first one. All mentioned methods are given with appropriate detailed algori&thms and links to the code placed in the Internet.