Нужен эвристический алгоритм заполнения таблицы или существует обычный?

Question

[akass]

Подскажите в какую сторону думать.
Нужно придумать алгоритм заполнения таблицы.
Нужно заполнить нужные ячейки, так чтобы в каждой строке было было заполнено N ячеек, в каждом столбце было заполнено M ячеек и чтобы каждая случайная пара ячеек повторялась встречалась в двух строках.

Comments

[Mr Crabbz]

Пример нарисуйте в ворде или любом граф.редакторе. Сейчас задача непонятна.

[Дмитрий Ковальский]

Роман Краббз: Видимо таблицу размером K*P хитро заполнить так чтобы в строке было N элементов, а в столбце M. Я бы добавил условие "не более чем", иначе придется доказывать что расстановка вообще существует.

[akass]

Роман Краббз: dl3.joxi.net/drive/0014/1643/939627/151127/a5b0f3f...

Answer 1

[Mrrl]

Сразу можно сказать, что число столбцов в таблице - L=M*(N-1)/2+1, число строк - K=M*L/N. Оба этих числа должны быть целыми.
В частном случае, когда N=q+1, M=2*(q+1), где q - простое число или степень простого, матрицу построить можно, в ней каждая строка будет встречаться дважды, а верхняя (и нижняя) половинка матрицы будет матрицей инцидентности конечной проективной плоскости. В остальных случаях - боюсь, что нужна эвристика, или вообще полный перебор. Всё-таки, это получается задача о покрытии - надо покрыть удвоенный набор рёбер полного графа с L вершинами непересекающимися графами с N вершинами. Свойство "в каждом столбце M ячеек" выполнится автоматически.