Передо мной стоит следующая задача. Есть некое множество элементов количеством 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.
Может быть, кто-нибудь знает, как к этой задаче можно подступиться? Или, может, существуют готовые решения, алгоритмы для моей или схожей задачи? Алгоритм генерации сочетаний у меня есть.

Здравствуйте, madmech, Вы писали:

Что-то ответа в теме нету, неужели неочевидный алгоритм? Или я где-то заблуждаюсь?

И так,

заведите массив, в котором на каждое число проставьте количество нужных попаданий в результат следующим методом:

Из 5-ти по 3, нужно 7 сочетаний:
1..... 2..... 3..... 4..... 5..... (индекс массива)
Заполняем массив нулями, затем последовательно увеличиваем цифры, начиная с самого маленького значения в массиве, выходя за правую границу - используем массив с начала:
0+1(1) 0+1(2) 0+1(3) 0..... 0..... первое сочетание 123
1+1(3) 1..... 1..... 0+1(1) 0+1(2) второе сочетание 145
2..... 1+1(1) 1+1(2) 1+1(3) 1..... третье 234
2+1(2) 2+1(3) 2..... 2..... 1+1(1) четвёртое 125
3..... 3..... 2+1(1) 2+1(2) 2+1(3) пятое 345
3+1(1) 3+1(2) 3+1(3) 3..... 3..... шестое 123 - конфликт
4-1(1) 4-1(2) 4-1(3) 3..... 3..... уменьшаем значения по индексам комбинации 123
3+1(1) 3+1(2) 3..... 3+1(3) 3..... шестое 124 (методом получения следующей комбинации последовательным сдвигом по массиву)
4+1(3) 4..... 3+1(1) 4..... 3+1(2) седьмое 135 (увеличиваем с минимальных значений в массиве) (итого, в массиве кол-во попаданий каждой цифры)
Итого
123
124
125
135
145
234
345

Или без проверки на конфликт, с использованием последовательного генератора:

Опять же - массив, заполнить можно быстро:
3*7= 21, индексов - 5, 21/5 =4(1) - всем элементам по 4, один, на усмотрение программы)), увеличить на единицу.
54444
Генерация/Остаток в массиве/сочетание
123/43344/1
124/32334/2
125/21333/3
134/11223/4
135/01122/5
145/не подходит, кол-во возможных единиц превышено
234/00012/6 - здесь видим, что дальнейшие сочетания невозможны, осталось лишь две цифры 4,5
откатываем последнее состояние массива по отобранным комбинациям, продолжаем с 135/01122/5
235/00021/6 - здесь видим, что дальнейшие сочетания невозможны, осталось лишь две цифры 4,5
откатываем последнее состояние массива по отобранным комбинациям, продолжаем с 135/01122/5
245/00111/6
345/00000/7

Здравствуйте, madmech, Вы писали:

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

Идея алгоритма: пусть M = НОК(n,k). Тогда цепочка "123...n"*(M/n) может быть нарублена на M/k уникальных кусочков — сочетаний длиной k.
Причём частоты всех элементов одинаковы (ровно по M/n раз).

Если C<=(M/k), так и делаем.
12 34 51 23 45

Понятно, что одной такой серии нам может не хватить.
Поэтому совершим перестановку над "123...n", так, чтобы изменения затронули все возможные способы нарубки.

Пусть D = НОД(n,k). Если он больше 1, то достаточно прокрутить — "23...n1", "3...n12" и т.д.
Это даст нам уже (M/k)*D сочетаний.
(Правда, если n=k, сочетание будет одно-единственное, поскольку от порядка элементов в кусочке оно не меняется).

Для примера, пусть n=10, k=4, M=20, D=2
1234 5678 9012 3456 7890
2345 6789 0123 4567 8901

Теперь нужно подумать над другими классами перестановок. Проворот уже назвал...

При составлении кругового турнира (из 2n по 2) есть очень несложный способ, как сделать 2n-1 разбиение участников на n пар.

1  2  3  4  5  6  7  8
9 10 11 12 13 14 15 16

1  3  4  5  6  7  8 16
2  9 10 11 12 13 14 15

1  4  5  6  7  8 16 15
3  2  9 10 11 12 13 14

и т.д.

Что-то похожее можно изобразить, обобщив на k рядов?