Клеточно-автоматные алгоритмы пермутации матриц

В формализации клеточных автоматов описываются четыре алгоритма, перемешивающих элементы матрицы на основе циклических сдвигов строк и столбцов. Один из алгоритмов показывает интересное поведение при нечётном порядке матрицы n, прикотором после пермутаций матрица претерпевает поворот на ±90∘ и на 180∘ (отражение относительно центра), а рост периода N оказывается быстрее экспоненциального. Исходя из соображений индукции короткого ряда n = 3, 5, . . . , 11, высказана гипотеза, что N равно наименьшему общему кратному всех нечётных чисел, не превосходящих 2n, т.е. N = НОК(3, 5, . . . , 2n - 1). Приведены аргументы для объяснения гипотезы. Динамика пермутаций анализируется с помощью введенных авторами двух «метрик», отражающих степень перемешанности. Результаты работы могут быть использованы при генерации псевдослучайных чисел.