Задачка из жизни. Почти комбинаторика. Но не совсем...
От: ta_and  
Дата: 03.12.03 08:07
Оценка:
Есть массив из 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.
Возможно этот вариант решения не оптимален.
Но уж чем богаты....
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.