Ячеистая структура перестановочной диаграммы

Если проанализировать диаграммы, представленные на рис. 7.3, или данные табл. 7.1, то обнаружится их повторяющийся характер, что иллюстрируется на рис. 7.4. Выполняя разбиение перестановочной диаграммы для N = 32 на четыре ромбовидные ячейки и соединяя между собой атомы в пределах каждой ячейки, чтобы подчеркнуть форму соответствующих фигур, обнаруживаем наличие кристаллической структуры, периодически повторяющейся на непрямоугольном базисе в обоих направлениях. Интересно отметить, что контур фигуры в каждой ячейке повторяет по форме перестановочную диаграмму для N = 8, но по сравнению с последней имеет в два раза больший масштаб. Теперь если масштаб полной диаграммы для N = 32 увеличить в два раза, то получим периодически повторяющуюся структуру, соответствующую диаграмме, для которой N = 128.

Для нечетных показателей степени имеем одно семейство диаграмм, а для четных -другое семейство. Данная топология совсем не является очевидной из определения алгоритма, иллюстрируемого на рис. 7.2, но проявляется в явном виде в случае, когда мы располагаем информацией о числе перестановочных матриц с целью соответствующей проверки. Очевидно, имеются два семейства ячеек; семейство I включает в себя ячейки, содержащие по четыре атома, в совокупности образующие фигуру, напоминающую бумажного змея, тогда как семейство состоит из ячеек, содержащих восемь атомов, расположенных в форме лягушки. Легко убедиться в правомерности следующих характеристик:

Хотя диаграммы обоих типов, соответствующие этим двум семействам, в явном виде иллюстрируют наличие ячеистой конфигурации периодического характера, структура, получаемая при замене каждой ячейки точкой, не является достаточно регулярной и должна быть подвергнута исследованию. На перестановочной диаграмме для отметим нижние левые элементы каждой из ячеек. Легко убедиться в том, что координаты элемента в строке при

Рис. 7.4. При перестановочная диаграмма подобна кристаллической решетке с четырьмя ячейками, каждая из которых состоит из восьми атомов.

Коэффициент 4 обусловлен тем, что шаг решетки атомов в пределах одной ячейки равен Подстрочный индекс 4 означает число ячеек вдоль одной оси координат. Так как общее количество атомов равно N, а в ячейке содержится 4 или 8 атомов, то полное число ячеек составляет или 8), а число ячеек вдоль одной оси координат есть корень квадратный из этой величины:

Шаг решетки в пределах одной ячейки равен «ширине» этой ячейки деленной на число содержащихся в ней атомов (т. е. на 4 или 8), и таким образом равен чем и обусловлено двукратное появление числа 4 в уравнениях для координат элементов ячеек. В общем случае имеем

Описанная здесь топологическая структура является основой алгоритма быстрой перестановки FASTPERMUTE, рассматриваемого ниже.

Медленная перестановка, которая является традиционной, выполняется следующим образом. Для определения при заданных и N осуществляются двоичное представление с использованием Р двоичных разрядов, а затем запись элементов полученного числа в обратном порядке их следования и возвращение к десятичному представлению этого числа. Например, нам известно, что для N = 16 имеем: . Двоичным представлением числа является , а числа .

Удобный способ выполнения перестановки путем изменения порядка следования двоичных символов на обратный в случае, когда краткость записи более предпочтительна, чем скорость реализации

этой процедуры, в формализованном представлении имеет вид

Функция преобразует ее десятичный аргумент в двоичное число, состоящее из 16 цифр; функция осуществляет изменение порядка следования этих цифр, составляющих аргумент данной функции, на обратный, а процедура обеспечивает преобразование полученного таким образом двоичного числа в десятичное.