Я хочу создать особый тип комбинации, в котором никакие два набора не имеют более одного пересекающегося элемента. Позвольте мне объяснить на примере:
Если вы создадите стандартные не повторяющиеся комбинации из трех букв, у вас будут 9C3-множества.
Они будут содержать такие множества, как ABC, ABD, BCD и т.д. Я ищу для создания наборов, которые содержат не более одной общей буквы. Итак, в этом примере мы получим следующие множества:
ABC, ADG, AEI, AFH, BEH, BFG, BDI, CFI, CDH, CEG, DEF и GHI - обратите внимание, что если вы берете любые два набора, то не более 1 повторяющейся буквы.
Что было бы хорошим способом создания таких множеств? Это должно быть масштабируемое решение, так что я могу сделать это для набора из 1000 букв, с дополнительным размером 4.
Любая помощь приветствуется.
Ответ 2
Скажем, у вас есть n писем (или студентов или что-то еще), и каждую неделю хочется разбить их на подмножества размера k (в общей сложности подмножества n/k каждую неделю). Этот метод будет генерировать почти n/k подмножества каждую неделю - я покажу ниже, как его расширить, чтобы генерировать точно n/k подмножества.
Создание подмножеств (без разбиения на разделы)
Сначала выберите p, наибольшее простое число <= n/k.
Рассмотрим каждую упорядоченную пару (a, b) такую, что
0 <= a < k
0 <= b < p
Мы можем сопоставить каждое спаривание с одной из наших букв; таким образом, мы можем сопоставить p*k <= n буквы таким образом (опять же, я покажу ниже, как отображать ровно n букв)
(0,0) => 'A'
(0,1) => 'B'
...
(0,p-1) => 'F'
(1,0) => 'G'
(1,1) => 'H'
...
(k-1,p-1) => 's'
Теперь, учитывая
0 <= w < p
0 <= i < p
Мы можем создать набор S w (i) наших упорядоченных пар. Каждое спаривание в S w (i) будет представлять одну букву (согласно нашему отображению выше), а множество S w (i) само представляет собой "группировку букв", ака. одно подмножество размера k.
Формула для S w (i) есть
Sw(i) = {(0,i mod p), (1,(w+i) mod p), (2,(2w+i) mod p),..., ((k-1),((k-1)*w+i) mod p)}
= { (x,y) | 0 <= x < k and y = w*x + i (mod p)}
Если мы изменим w и я на все возможные значения, получим p 2 полные множества. Когда мы возьмем любые два из этих множеств, они будут иметь не более одного пересекающегося элемента.
Как это работает
Скажем, что у нас есть два набора S w1 (i 1) и S w2 (i 2). Если S w1 (i 1) и S w2 (i 2), имеют более одного элемента, то существует не менее двух x таких, что
w1*x + i1 = w2*x + i2 (mod p)
(w1-w2)*x + (i1-i2) = 0 (mod p)
Однако любой, кто взял модульную арифметику, знает, что если p является простым, либо x имеет единственное решение, либо (w 1= w 2 и я 1= я 2); таким образом, не может быть больше одного x и S w1 (i 1) и S w2 (i 2) может иметь не более одного пересекающегося элемента.
Анализ
Так как p < n/k, теорема Чебышева (в которой говорится, что между x и 2x при x > 3 существует простое число)
n/2k < p <= n/k
Таким образом, этот метод генерирует по крайней мере (n/2k) 2 подмножества букв, хотя на практике p будет ближе к n/k, поэтому число будет ближе к (n/k ) 2. Поскольку простая верхняя граница для максимально возможных таких подмножеств n(n-1)/(k(k-1)) (см. Комментарий BlueRaja ниже), это означает, что алгоритм асимптотически оптимален и будет генерировать около оптимального количества множеств (даже в худшем случае он не будет генерируйте менее чем 1/4 оптимальной суммы, см. комментарий ниже)
Разметка
Теперь вы хотите группировать буквы в разделы каждую неделю: каждую неделю все буквы включаются в одну группу.
Мы делаем это, позволяя фиксировать w на определенное значение (представляющее неделю) и позволяя i варьироваться от 0 до p-1.
Proof
Рассмотрим группы, которые мы создали:
Sw(i) = { (x,y) | 0 <= x < k and y = w*x + i (mod p)}
Скажем, w фиксировано и i изменяется от 0 до p-1. Тогда мы получим p-множества:
Sw(0), Sw(1), ..., Sw(p-1)
Теперь скажем S w (i 1) и S w (i 2) (с я 1 =/= я 2) пересекаются; затем
w*x + i1 = w*x + i2 (mod p)
для некоторого x, и, следовательно, я 1= я 2. Таким образом, S w (i 1) и S w (i 2) не пересекаются.
Так как ни одно из наших множеств не пересекается, и их ровно p (каждый с k элементами), наши множества образуют разбиение букв k * p.
Создание n/k подмножеств каждую неделю
Самый большой недостаток этого метода заключается в том, что он генерирует множества для букв p * k, а не n букв. Если последние буквы не могут быть опущены (как в вашем случае, когда буквы являются учащимися), есть две возможности генерировать ровно n/k подмножеств каждую неделю:
-
Найдите набор простых чисел p 1, p 2, p 3,... который суммирует до точности п/к. Тогда мы можем рассматривать каждую группу p i k букв как независимый алфавит, так что вместо нахождения подмножеств pk-букв мы найдем одну группу подмножеств для p 1 * k букв, другая группа подмножеств для p 2 * k букв, другая группа...
Это имеет тот недостаток, что письма из одной группы никогда не будут соединены с письмами из другой группы, что уменьшит общее количество генерируемых подмножеств. К счастью, если n равно, гипотеза Голдбаха † вам понадобится только две группы (если n нечетно, вам понадобится три не более)
Этот метод гарантирует подмножества размера k, но не генерирует столько подмножеств.
† Несмотря на то, что он недоказан, он известен как истина для каждого смехотворно большого числа, с которым вы, вероятно, столкнетесь с этой проблемой.
-
Другой вариант - использовать наименьшее простое p >= n/k. Это даст вам p * k >= n букв - после того, как подмножества были сгенерированы, просто выкиньте лишние буквы. Таким образом, в конце это дает вам некоторые подмножества с размером < к. Предполагая, что k делит n равномерно (т.е. N/k является целым числом), вы можете взять меньшие подмножества и вручную смешать их для создания подмножеств размера k, но вы рискуете иметь некоторое совпадение с прошлыми/будущими подмножествами таким образом. < ш > Этот метод генерирует по меньшей мере столько подмножеств, что и исходный метод, но некоторые могут иметь размер < к
Пример
Возьмем n = 15, k = 3. т.е. есть 15 учеников, и мы делаем группы из трех.
Начнем с того, что мы выбираем наибольшее простое число p <= n/k. n/k является простым (повезло нам!), поэтому p = 5.
Мы отобразим 15 учеников в упорядоченные пары (a, b), описанные выше, давая нам (каждое письмо является студентом):
(0,0) = A
(0,1) = B
(0,2) = C
(0,3) = D
(0,4) = E
(1,0) = F
(1,1) = G
(1,2) = H
(1,3) = I
(1,4) = J
(2,0) = K
(2,1) = L
(2,2) = M
(2,3) = N
(2,4) = O
Метод генерирует 25 групп из трех. Таким образом, поскольку нам нужно планировать n/k = 5 групп каждую неделю, мы можем запланировать 5 недель активности (5 групп в неделю * 5 недель = 25 групп).
В течение недели 0 мы создаем раздел как
S0(i), for i = 0 to 4.
S0(0) = { (0,0), (1,0), (2,0) } = AFK
S0(1) = { (0,1), (1,1), (2,1) } = BGL
S0(2) = { (0,2), (1,2), (2,2) } = CHM
S0(3) = { (0,3), (1,3), (2,3) } = DIN
S0(4) = { (0,4), (1,4), (2,4) } = EJO
На четвертую неделю будет
S4(i) for i = 0 to 4.
S4(0) = { (0,0), (1, (4*1 + 0) mod 5), (2, (2*4 + 0) mod 5) }
= { (0,0), (1,4), (2,3) }
= AJN
S4(1) = { (0,1), (1, (4*1 + 1) mod 5), (2, (4*2 + 1) mod 5) }
= { (0,1), (1,0), (2,4) }
= BFO
S4(2) = { (0,2), (1, (4*1 + 2) mod 5), (2, (4*2 + 2) mod 5) }
= { (0,2), (1,1), (2,0) }
= CGK
S4(3) = { (0,3), (1, (4*1 + 3) mod 5), (2, (4*2 + 3) mod 5) }
= { (0,3), (1,2), (2,1) }
= DHL
S4(4) = { (0,4), (1, (4*1 + 4) mod 5), (2, (4*2 + 4) mod 5) }
= { (0,4), (1,3), (2,2) }
= EIM
Здесь график на все 5 недель:
Week: 0
S0(0) ={(0,0) (1,0) (2,0) } = AFK
S0(1) ={(0,1) (1,1) (2,1) } = BGL
S0(2) ={(0,2) (1,2) (2,2) } = CHM
S0(3) ={(0,3) (1,3) (2,3) } = DIN
S0(4) ={(0,4) (1,4) (2,4) } = EJO
Week: 1
S1(0) ={(0,0) (1,1) (2,2) } = AGM
S1(1) ={(0,1) (1,2) (2,3) } = BHN
S1(2) ={(0,2) (1,3) (2,4) } = CIO
S1(3) ={(0,3) (1,4) (2,0) } = DJK
S1(4) ={(0,4) (1,0) (2,1) } = EFL
Week: 2
S2(0) ={(0,0) (1,2) (2,4) } = AHO
S2(1) ={(0,1) (1,3) (2,0) } = BIK
S2(2) ={(0,2) (1,4) (2,1) } = CJL
S2(3) ={(0,3) (1,0) (2,2) } = DFM
S2(4) ={(0,4) (1,1) (2,3) } = EGN
Week: 3
S3(0) ={(0,0) (1,3) (2,1) } = AIL
S3(1) ={(0,1) (1,4) (2,2) } = BJM
S3(2) ={(0,2) (1,0) (2,3) } = CFN
S3(3) ={(0,3) (1,1) (2,4) } = DGO
S3(4) ={(0,4) (1,2) (2,0) } = EHK
Week: 4
S4(0) ={(0,0) (1,4) (2,3) } = AJN
S4(1) ={(0,1) (1,0) (2,4) } = BFO
S4(2) ={(0,2) (1,1) (2,0) } = CGK
S4(3) ={(0,3) (1,2) (2,1) } = DHL
S4(4) ={(0,4) (1,3) (2,2) } = EIM
Более практичный пример
В вашем случае n = 1000 студентов и k = 4 в каждой группе. Таким образом, мы выбираем p как самое большое простое число lt = = (n/k = 1000/4 = 250), поэтому p = 241. Без учета вышеперечисленных изменений под "Генерация n/k подмножеств каждую неделю" , этот метод будет генерировать расписание для 961 студентов продолжительностью 241 неделя.
(Верхняя граница для максимального количества возможных подмножеств будет 1000 * 999/(4 * 3) = 83250, хотя фактическое число, вероятно, меньше этого. Тем не менее, этот метод генерирует подмножества 58081 или около 70% от теоретического максимума!)
Если мы используем первый метод выше для создания расписания для ровно 1000 учеников, мы берем p 1= 113, p 2= 137 (так что p 1 + p 2= n/k). Таким образом, мы можем генерировать (113) ^ 2 + (137) ^ 2 = 31 538 подмножеств студентов, что достаточно, чтобы продлиться 113 недель.
Если мы используем второй метод, приведенный выше, чтобы создать график для ровно 1000 учеников, мы возьмем p = 251. Это даст нам график для 1004 студентов в течение 251 недели; мы удаляем учащихся из 4 phantom из расписания каждую неделю. Обычно это приводит к четырем группам по 3 раза в неделю (хотя это маловероятно, также возможно иметь, например, одну группу из 2 и 2 групп по 3). Группы с < 4 ученика всегда будут иметь общее число учащихся в 4 из 4 человек, поэтому вы можете вручную разместить этих учащихся по группам из 4 человек, рискуя потенциально связать двух из этих учеников позже в другой группе.
Заключительные мысли
Один из недостатков этого алгоритма заключается в том, что он не очень гибкий: если студент выпадает, мы навсегда застреваем с учеником phantom. Кроме того, нет возможности добавить новых студентов в расписание на полпути за год (если мы не разрешим их, изначально создавая студентов phantom).
Эта проблема относится к категории систем с ограниченным множеством в комбинаторике. Подробнее см. эту статью, особенно главы 1 и 2. Поскольку это файл постскриптума, вам понадобится gsview или что-то для его просмотра.
