ОПИСАНИЕ КОМБИНАТОРНОГО АЛГОРИТМА ПЕРЕЧИСЛЕНИЯ УПОРЯДОЧЕННЫХ МУЛЬТИПЛИКАТИВНЫХ РАЗЛОЖЕНИЙ
Статья посвящена решению комбинаторной задачи – систематическому перечислению всех объектов определенного вида. В качестве объекта для перечисления принято разложение целого числа r>1 в упорядоченное произведение n целых сомножителей (так называемый n-профиль числа r). Использование рассматриваемых объектов для проектирования генераторов псевдослучайных последовательностей определяет актуальность статьи. Целью статьи является создание комбинаторного алгоритма систематического перечисления всех n-профилей числа r . Для достижения цели выполнена формальная постановка задачи, проведен ее анализ, в котором введено понятие характеристической матрицы n-профиля r и установлено взаимно однозначное соответствие межу профилями и характеристическими матрицами, что позволило от перечисления профилей перейти к перечислению характеристических матриц, с последующим преобразованием их в профили. На множестве характеристических матриц введено отношение B-эквивалентности, позволяющее разбить его на классы и перечислять элементы выбранного класса B-эквивалентности независимо от остальных характеристических матрицы. Показано, что порождение B-эквивалентной характеристической матрицы есть процесс определения ее элементов путем распределения единиц кратностей простых множителей в каноническом разложении числа r и подробно рассмотрен этот процесс. На этапе синтеза результаты анализа задачи воплощены в искомый алгоритм. Приведен пример перечисления n-профилей числа r с использованием этого алгоритма.
Румбешт В.В., Бурданова Е.В. Описание комбинаторного алгоритма перечисления упорядоченных мультипликативных разложений // Научный результат. Информационные технологии. – Т.11, №3, 2026. – С. 100-111. DOI: 10.18413/2518-1092-2026-11-3-0-9
Пока никто не оставил комментариев к этой публикации.
Вы можете быть первым.