Есть массив из N различных элементов.
Разместить эти N элементов в M групп по K элементов L раз, таким образом, чтобы каждый элемент встретился с каждым элементом хотя бы в одной группе.
Количество L должно быть минимизировано.
Количество встреч элемента с уже встречавшимися элементами должно быть минимизировано.
М не равно К.
N = K * M
K > 1
M > 1
Необходим АГОРИТМ или МАТИМАТИЧЕСКИ ОБОСНОВАННЫЙ ПРИМЕР.
Решение мною до сих пор не найдено... ( распределяю ручками. наугад.

Пример из практики.
Дано:
N = 6 элементы 1 2 3 4 5 6
M = 2 две группы
K = 3 по три элемента в группе
Решение:
L=1

1 4
2 5
3 6
--------------
L=2

1 2
4 3
5 6
--------------
L=3

1 2
3 5
4 6
--------------
L=4

1 3
2 5
4 6

Минимальное количество сочетаний — 4.
Возможно этот вариант решения не оптимален.
Но уж чем богаты....

Видимо очень сложная задачка...
Раз никто не смог за это время найти хотя-бы какое-нибудь приемлемое решение...

Здравствуйте, Аноним, Вы писали:

А>Видимо очень сложная задачка...
А>Раз никто не смог за это время найти хотя-бы какое-нибудь приемлемое решение...

Хммм. Вот какая идея: рассмотрим целевую матрицу инцедентности (какие элементы с какими соединены), размером N*(N-1).
Каждый раз мы частично покрываем её реальными матрицами K*(K-1), в количестве M штук.

  1 2 3 4 5 6
1 \ a a
2 a \ a
3 a a \
4       \ b b
5       b \ b
6       b b \

a = {1,2,3}
b = {4,5,6}


  1 2 3 4 5 6
1 \     c c
2   \ d     d
3   d \     d
4 c     \ c
5 c     c \
6   d d     \

c = {1,4,5}
d = {2,3,6}

Общая площадь одного покрытия S = M*K*(K-1) = N*(K-1).
Внутри одного покрытия эти матрицы не пересекаются, поскольку мы разбиваем множество на непересекающиеся части. Поэтому S =, а не <=
А вот покрытия между собой могут пересекаться.

Отсюда L >= ]N*(N-1)/S[ = ]N*(N-1)/(N*(K-1))[
L >= ](N-1)/(K-1)[
Это — оценка снизу.

L(6, 2 по 3) >= (6-1)/(3-1) = 5/2 = 2.5
L >= 3