Как определить, является ли трехмерный квадрат латинским?
Мне нужно разработать алгоритм, который говорит, является ли данная матрица целых чисел действительным латинским квадратом или нет. Я никогда не работал с латинскими Sqares раньше, поэтому я не знаю, с чего начать. После некоторых исследований я нашел только алгоритмы для написания латинского квадрата. Единственное, что произошло со мной, это то, что сумма всех столбцов и строк должна быть одинаковой, но тогда я должен проверить каждое число, если оно повторяется в той же строке и столбце. При таком подходе программа будет стоить очень много времени. Я использую C ++.
Решение
При таком подходе программа будет стоить очень много времени.
Нет, так как вы можете отклонить много матрицы, прежде чем вы достигнете конца. Так что алгоритм быстро потерпит неудачу. Худшая оценка рабочего алгоритма O(n*(n+1)) (Я предполагаю, что вы оцениваете только квадратную матрицу, где размерность равна n * n). Но средний алгоритм будет намного лучше — потому что он потерпит неудачу, как было найдено в первом равенстве.
Обновить:
Средняя сложность может быть грубой и приблизительно оценена как число реальных латинских квадратов к числу возможных квадратов. Для этого нужно ввести понять normalized площадь. Два квадрата ниже интуитивно одинаковы:
[ 1 2 [5 7
2 1 ] 7 5]
Таким образом, чтобы нормализовать это, мы можем использовать подстановку для чисел 1 … n из n * n квадрат. Итак, первая форма выигрывает.
Для нормализованных квадратов Вики дает оценку 
Ты боишься? Но для среднего нам также нужно разделить эту формулу на общее количество матриц. Для этого посмотрите эту формулу http://en.wikipedia.org/wiki/Combination
Другие решения
Других решений пока нет …