Возникла проблема с генерацией заданного количества сочетаний

← →
madmech © (2010-06-09 18:34) [0]

Передо мной стоит следующая задача. Есть некое множество элементов количеством n. Нужно сформировать заранее заданное количество случайных сочетаний (С из n по k) данного множества. Разумеется, предполагается, что это предустановленное количество должно быть значительно меньше общего числа сочетаний. Дополнительным требованием выступает необходимость совпадения частот, ну или хотя бы их близости, попадания каждого элемента во все подмножества (сочетания). Вторым требованием является обязательное наличие каждого элемента в хотя бы одном сочетании получившегося семейства сочетаний. Поясню на примере. Есть некое стартовое множество, состоящее из 5 элементов, каждый из которых для условности пронумеруем по порядку от 1 до 5. И надо сформировать 5 сочетаний по 2 элемента в каждом с указанными выше требованиями. Общее количество сочетаний: С из 5 по 2 = 10. В итоге должно получиться что-то вроде этого:
1.(1, 2)
2.(3, 4)
3.(2, 5)
4.(1, 4)
5.(3, 5)

Как видим, при данных стартовых условиях задачи частоты у всех элементов совпадают и равны 2.
Может быть, кто-нибудь знает, как к этой задаче можно подступиться? Или, может, существуют готовые решения, алгоритмы для моей или схожей задачи? Алгоритм генерации сочетаний у меня есть

← →
Sha © (2010-06-09 19:39) [1]

Вероятно, решения в общем случае нет.
Решения частных случаев (k=2, k=3) встречались.

← →
Sha © (2010-06-09 20:03) [2]

Не обратил внимания на то, что у тебя отсутствует требование
недопустимости повторения пар в разных кортежах.
В этом случае задача сильно упрощается.

P.S.
К Дельфи вопрос отношения не имеет, можно в Прочее перенести.

← →
madmech © (2010-06-10 13:15) [3]

> Не обратил внимания на то, что у тебя отсутствует требование
> недопустимости повторения пар в разных кортежах.

А почему именно пар, а не, например, троек или четверок? Поясни свою мысль, а то, честно говоря, недопонял, что ты хотел сказать.

P.S. А как тему перенести в раздел "Прочее"?

вот неадаптированный кусок прикладного алгоритма.
генерит комбинации по списку xml узлов

procedure ComposeAllVariants(AXml : IXMLDOMDocument2); var iList : IXMLDomNodeList; iNode : IXMLDomNode; i,nMembers,idx,idx1,n : integer; lArr : array of integer; begin //Получаем полный список сущностей, из которых делаются комбинации iList := AXml.selectNodes("/certs/docs/simple/cert"); if (iList <> nil) and (iList.length > 1) then begin //Комбинации могут состоять из двух и более сущностей for nMembers := 2 to iList.length do begin for i := 0 to Pred(iList.length) do begin //Устанавливаем длину динамического массива равной длине очередной комбинации SetLength(lArr,nMembers); n := 0; for idx1 := i to pred(i + pred(nMembers)) do begin lArr[n] := idx1; //Вносим в массив (комбинацию) очередную сущность inc(n); end; for idx := (i + pred(nMembers)) to pred(iList.length) do begin lArr[pred(length(lArr))] := idx; //Регистрация комбинации (в массиве лежат индексы сущностей входящих в комбинацию) AddVariant(lArr); end; end; end; end; end;

> madmech © (10.06.10 13:15) [3]
> А почему именно пар, а не, например, троек или четверок?

Потому, что есть целый класс похожих задач.

Например, вот одна их известных задач на эту тему.

В детском саду N детей. Каждый день воспитательница
выводит их на прогулку строем по K детей в шеренге,
т.е. образует N/K кортежей по K детей.
Требуется составить такое расписание прогулок,
чтобы в течение (N-1)/(K-1) дней каждый ребенок
в своей шеренге увидел остальных.

Возникла проблема с генерацией заданного количества сочетаний Найти похожие ветки