Комментарии 9
А не проще взять таблицу умножения для любой группы нужного порядка (проще всего, конечно, сгенерировать для циклической группы) и перетасовать столбцы/строки случайным образом?
На самом деле метод Джейкобсона и Мэтьюза в некоторой степени является вариацией того, что вы предложили :) Разница лишь в том, что в вашем предложении нет гарантий того, что вероятность попадания каждой цифры в каждую ячейку равномерна.
Плюс, есть у меня такое ощущения, что таким образом у вас получится сгенерировать не каждый квадрат. Тут примерно как с кубиком Рубика, предложенные вами преобразования будут давать лишь подмножество множества всех корректных латинских квадратов. Хотя это надо отдельно доказывать, конечно.
Я имел в виду что-то такое (пример на питоне):
import numpy
N = 10
idx1 = idx2 = numpy.arange(N)
numpy.random.shuffle(idx1)
numpy.random.shuffle(idx2)
A = numpy.fromfunction(lambda i, j: (idx1[i] + idx2[j]) % N, (N, N), dtype=int)А, тогда это метод Косельни, только на основе двух массивов. Проблема та же самая что и у Косельни — итоговое распределение не равномерное. Особенно будет заметно на больших квадратах.
Вообще нужно очень аккуратно складывать случайные значения. Хотя сами по себе они равномерно распределены, но по центральной предельной теореме у вас в итоге получится распределение, приближающееся к нормальному.
В целом такой вариант мог бы использоваться для игр, я согласен :)
Вот здесь есть подробная работа (диссертация) на тему перемешивания и генерации случайных латинских квадратов. Там показываются недостатки наивного метода (в первую очередь, проблемы с равномерностью распределения, во вторую -- с эффективностью) на больших квадратах. Метод Джекобсона-Мэтьюза один из оптимальных по своим характеристикам.
А автору статьи спасибо за чудесную визуализацию метода!
итоговое распределение не равномерное
Почему?
Вообще нужно очень аккуратно складывать случайные значения. Хотя сами по себе они равномерно распределены, но по центральной предельной теореме у вас в итоге получится распределение, приближающееся к нормальному.
Если вас смутила запись (idx1[i] + idx2[j]) % N, то это просто компактная форма записи умножения для циклической группы. В этом месте можно было бы написать B[idx1[i], idx2[j]], где B — это таблица умножения некоторой группы соответствующего порядка. И, кстати, так как сложение происходит по модулю, то предельная теорема тут не применима.
PS. Кстати, можно еще ввести третий случайный массив idx3 и перемешивать результат умножения lambda i, j: idx3[(idx1[i] + idx2[j]) % N]
Статья супер! Спасибо!
Латинский квадрат: вызываем демонов во имя математики