Скажем, у вас есть n букв (или студентов, или что-то еще), и каждую неделю вы хотите разделить их на подмножества размера k (всего n/k подмножеств каждую неделю). Этот метод будет генерировать почти n/k подмножества каждую неделю - ниже я покажу, как расширить его, чтобы генерировать ровно n/k подмножества.
Генерация подмножеств (без разделения)
Первый выбор p, наибольшее простое число <= n / k. </p>
Рассмотрим каждую упорядоченную пару (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) равна
S<sub>w</sub>(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 и i по всем возможным значениям, мы получаем p 2 полных наборов. Когда мы возьмем любой два из этих наборов, они будут иметь не более одного пересекающегося элемента.
Как это работает
Скажем, у нас есть два набора S w1 (i 1 ) и S w2 (i 2 ). Если S w1 (i 1 ) и S w2 (i 2 ) имеют более одного общего элемента, то существует минимум два x такие, что
w<sub>1</sub>*x + i<sub>1</sub> = w<sub>2</sub>*x + i<sub>2</sub> (mod p)
(w<sub>1</sub>-w<sub>2</sub>)*x + (i<sub>1</sub>-i<sub>2</sub>) = 0 (mod p)
Однако любой, кто принимается за модульную арифметику, знает, что если p простое число, либо x имеет уникальное решение, либо (w 1 = w 2 и i 1 = i 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.
Доказательство
Рассмотрим группы, которые мы создали:
S<sub>w</sub>(i) = { (x,y) | 0 <= x < k and y = w*x + i (mod p)}
Допустим, w является фиксированным и i изменяется от 0 до p-1. Тогда мы получим p наборов:
S<sub>w</sub>(0), S<sub>w</sub>(1), ..., S<sub>w</sub>(p-1)
Теперь, скажем, S w (i 1 ) и S w (i 2 ) (с i 1 = / = i 2 ) пересекаются; то
w*x + i<sub>1</sub> = w*x + i<sub>2</sub> (mod p)
для некоторого x, и, следовательно, i 1 = i 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 , ..., который суммирует в точности n / k , Тогда мы можем рассматривать каждую группу из p i k букв как независимый алфавит, так что вместо того, чтобы находить подмножества p k букв, мы находим одну группу подмножеств для p 1 * k букв, другая группа подмножеств для p 2 * k букв, другая группа ...
Это имеет тот недостаток, что письма из одной группы никогда не будут сопряжены с письмами из другой группы, что уменьшает общее количество генерируемых подмножеств. К счастью, если n четное, по гипотезе Гольдбаха † вам понадобится не более двух групп (если n нечетно, вам понадобится только три максимум )
Этот метод гарантирует подмножества размера k, но не генерирует столько подмножеств.
† Хотя это не доказано, известно, что это верно для каждого смехотворно большого числа, которое вы, вероятно, встретите для этой проблемы
Другой вариант - использовать наименьшее простое число p> = n / k. Это даст вам p * k> = n букв - после генерации подмножеств просто выбросьте лишние буквы. Таким образом, в итоге это дает вам несколько подмножеств с размером Этот метод генерирует как минимум столько же подмножеств, что и исходный метод, но некоторые могут иметь размер
Пример * * тысяча сто девяносто восемь
Возьмем n = 15, k = 3. То есть, у нас 15 учеников, и мы делаем группы по три.
Для начала выберем наибольшее простое число p <= n / k. n / k <em>равно простое число (повезло нам!) , поэтому 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 мы создаем раздел как
S<sub>0</sub>(i), for i = 0 to 4.
S<sub>0</sub>(0) = { (0,0), (1,0), (2,0) } = AFK
S<sub>0</sub>(1) = { (0,1), (1,1), (2,1) } = BGL
S<sub>0</sub>(2) = { (0,2), (1,2), (2,2) } = CHM
S<sub>0</sub>(3) = { (0,3), (1,3), (2,3) } = DIN
S<sub>0</sub>(4) = { (0,4), (1,4), (2,4) } = EJO
Для 4 недели это будет
S<sub>4</sub>(i) for i = 0 to 4.
S<sub>4</sub>(0) = { (0,0), (1, (4*1 + 0) mod 5), (2, (2*4 + 0) mod 5) }
= { (0,0), (1,4), (2,3) }
= AJN
S<sub>4</sub>(1) = { (0,1), (1, (4*1 + 1) mod 5), (2, (4*2 + 1) mod 5) }
= { (0,1), (1,0), (2,4) }
= BFO
S<sub>4</sub>(2) = { (0,2), (1, (4*1 + 2) mod 5), (2, (4*2 + 2) mod 5) }
= { (0,2), (1,1), (2,0) }
= CGK
S<sub>4</sub>(3) = { (0,3), (1, (4*1 + 3) mod 5), (2, (4*2 + 3) mod 5) }
= { (0,3), (1,2), (2,1) }
= DHL
S<sub>4</sub>(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
S<sub>0</sub>(0) ={(0,0) (1,0) (2,0) } = AFK
S<sub>0</sub>(1) ={(0,1) (1,1) (2,1) } = BGL
S<sub>0</sub>(2) ={(0,2) (1,2) (2,2) } = CHM
S<sub>0</sub>(3) ={(0,3) (1,3) (2,3) } = DIN
S<sub>0</sub>(4) ={(0,4) (1,4) (2,4) } = EJO
Week: 1
S<sub>1</sub>(0) ={(0,0) (1,1) (2,2) } = AGM
S<sub>1</sub>(1) ={(0,1) (1,2) (2,3) } = BHN
S<sub>1</sub>(2) ={(0,2) (1,3) (2,4) } = CIO
S<sub>1</sub>(3) ={(0,3) (1,4) (2,0) } = DJK
S<sub>1</sub>(4) ={(0,4) (1,0) (2,1) } = EFL
Week: 2
S<sub>2</sub>(0) ={(0,0) (1,2) (2,4) } = AHO
S<sub>2</sub>(1) ={(0,1) (1,3) (2,0) } = BIK
S<sub>2</sub>(2) ={(0,2) (1,4) (2,1) } = CJL
S<sub>2</sub>(3) ={(0,3) (1,0) (2,2) } = DFM
S<sub>2</sub>(4) ={(0,4) (1,1) (2,3) } = EGN
Week: 3
S<sub>3</sub>(0) ={(0,0) (1,3) (2,1) } = AIL
S<sub>3</sub>(1) ={(0,1) (1,4) (2,2) } = BJM
S<sub>3</sub>(2) ={(0,2) (1,0) (2,3) } = CFN
S<sub>3</sub>(3) ={(0,3) (1,1) (2,4) } = DGO
S<sub>3</sub>(4) ={(0,4) (1,2) (2,0) } = EHK
Week: 4
S<sub>4</sub>(0) ={(0,0) (1,4) (2,3) } = AJN
S<sub>4</sub>(1) ={(0,1) (1,0) (2,4) } = BFO
S<sub>4</sub>(2) ={(0,2) (1,1) (2,0) } = CGK
S<sub>4</sub>(3) ={(0,3) (1,2) (2,1) } = DHL
S<sub>4</sub>(4) ={(0,4) (1,3) (2,2) } = EIM
Более практичный пример
В вашем случае n = 1000 студентов и k = 4 в каждой группе. Таким образом, мы выбираем p как наибольшее простое число <= (n / k = 1000/4 = 250), поэтому p = 241. Без учета изменений, приведенных выше в разделе <strong>«Создание подмножеств n / k каждую неделю» , этот метод создаст расписание для 961 студента продолжительностью 241 неделя.
(Верхняя граница для максимально возможного числа подмножеств будет 1000 * 999 / (4 * 3) = 83250, хотя фактическое число, вероятно, меньше этого. Тем не менее, этот метод генерирует 58081 подмножеств, или около 70% от теоретического максимума!)
Если мы используем первый метод выше, чтобы сгенерировать расписание для ровно 1000 учеников, мы берем p 1 = 113, p 2 = 137 (так что p 1 + р 2 = н / к). Таким образом, мы можем сгенерировать (113) ^ 2 + (137) ^ 2 = 31 538 подмножеств учеников, которых хватит на 113 недель.
Если мы используем второй метод выше, чтобы сгенерировать расписание для ровно 1000 учеников, мы берем р = 251. Это даст нам расписание для 1004 учеников на 251 неделю; мы удаляем 4 фантомных ученика из расписания каждую неделю. Как правило, это приводит к тому, что четыре группы по 3 в неделю (хотя маловероятно, возможно, например, иметь одну группу из 2 и две группы по 3). Группы с <4 студентами всегда будут иметь число учеников, кратное 4, так что вы можете вручную распределить этих учеников по четырем группам, что может привести к тому, что двое из этих учеников снова будут вместе позже в другой группе. </p>
Заключительные мысли
Один недостаток этого алгоритма в том, что он не очень гибкий: если ученик бросает учебу, мы навсегда останемся с фантомным учеником. Кроме того, нет никакого способа добавить новых учеников в расписание в середине года (если мы не позволим им изначально создать фантомных учеников).
Эта проблема подпадает под категорию систем с ограниченным множеством в комбинаторике. См. этот документ для получения дополнительной информации, особенно в главах 1 и 2. Поскольку это файл postscript, вам потребуется gsview или что-то еще для его просмотра.