R-пакет CayleyR решает головоломку TopSpin алгоритмом пересечения циклов

Вышла новая версия R-пакета CayleyR, предназначенного для решения перестановочных головоломок. Разработчики представили алгоритм, основанный на пересечении циклов в графах Кэли. Исходный код опубликован на arXiv и доступен на CRAN.

Основная цель пакета — головоломка TopSpin(n,k). Её пространство состояний представляет собой граф Кэли симметрической группы Sn, порождённый циклическим сдвигом и префиксной перестановкой. Алгоритм выполняет итеративный двунаправленный поиск: из начальной и целевой позиций генерируются случайные последовательности операций, формирующие циклы в графе Кэли. Пересечение этих циклов даёт соединяющий путь.

Если прямое пересечение не найдено, специальный мостик с дистанционным управлением сужает разрыв, и процесс повторяется. Такой подход позволяет эффективно находить решения даже для сложных конфигураций.

Реализация сочетает хеш-индексированное хранилище состояний на C++ с опциональным ускорением на GPU Vulkan. Это делает пакет производительным и пригодным для исследования крупных пространств состояний.

Пакет CayleyR уже доступен для установки из CRAN. Разработчики надеются, что инструмент будет полезен как для исследователей теории групп, так и для любителей головоломок.