Ответ 1

Мне пришлось добавить еще один ответ, поскольку другой был слишком длинным.

Если у вас есть следующие ограничения:

1) Вам нужны группы по 4 раза в неделю.

2) Каждая группа в течение определенной недели не пересекается, и каждый ученик находится в одной группе.

3) Если два ученика находятся в одной группе, они не могут находиться в одной и той же группе в будущем.

Если вы построите граф G следующим образом:

1) Каждый ученик node.

2) Два ученика соединены краем, если раньше они не были вместе в группе.

Когда студенты отказываются/присоединяются произвольно, это становится трудной проблемой! Несмотря на то, что вы начинаете с полного графика, через несколько недель, график может стать довольно непредсказуемым.

Ваша проблема: вам нужно найти охватывающий подграф G, такой, что это объединение копий K_4 или, другими словами, разбиение на K_4s.

К сожалению, похоже, что эта проблема NP-Hard: точная крышка с помощью 4-х наборов (которая NP-Complete) может быть сведена к вашей проблеме (так же, как точная крышка на 3 набора может быть уменьшена до разбиения на треугольники).

Возможно, это поможет дать некоторые алгоритмы aproximation: http://www.siam.org/proceedings/soda/2010/SODA10_122_chany.pdf

(Ваша проблема может быть сведена к сопоставлению Hypergraph, и поэтому алгоритмы для этого могут быть использованы для вашей проблемы).

Точная обложка: http://en.wikipedia.org/wiki/Exact_cover

Разделение на треугольники: https://noppa.tkk.fi/noppa/kurssi/t-79.5103/viikkoharjoitukset/T-79_5103_solutions_5.pdf

Точная крышка на 4 множества = Учитывая набор S размера 4m и набор C из 4-элементных подмножеств S, существует ли подмножество C 'из C, такое, что каждый элемент из S появляется ровно один раз в C'.

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

Ответ 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 ² полные множества. Когда мы возьмем любые два из этих множеств, они будут иметь не более одного пересекающегося элемента.

Как это работает

Скажем, что у нас есть два набора S _w1 (i ₁) и S _w2 (i ₂). Если S _w1 (i ₁) и S _w2 (i ₂), имеют более одного элемента, то существует не менее двух x таких, что

w1*x + i1 = w2*x + i2 (mod p)  
(w1-w2)*x + (i1-i2) = 0 (mod p)

Однако любой, кто взял модульную арифметику, знает, что если p является простым, либо x имеет единственное решение, либо (w ₁= w ₂ и я ₁= я ₂); таким образом, не может быть больше одного x и S _w1 (i ₁) и S _w2 (i ₂) может иметь не более одного пересекающегося элемента.

Анализ

Так как p < n/k, теорема Чебышева (в которой говорится, что между x и 2x при x > 3 существует простое число)

n/2k < p <= n/k

Таким образом, этот метод генерирует по крайней мере (n/2k) ² подмножества букв, хотя на практике p будет ближе к n/k, поэтому число будет ближе к (n/k ) ². Поскольку простая верхняя граница для максимально возможных таких подмножеств 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 ₁) и S _w (i ₂) (с я ₁ =/= я ₂) пересекаются; затем

w*x + i1 = w*x + i2 (mod p)

для некоторого x, и, следовательно, я ₁= я ₂. Таким образом, S _w (i ₁) и S _w (i ₂) не пересекаются.

Так как ни одно из наших множеств не пересекается, и их ровно p (каждый с k элементами), наши множества образуют разбиение букв k * p.

Создание n/k подмножеств каждую неделю

Самый большой недостаток этого метода заключается в том, что он генерирует множества для букв p * k, а не n букв. Если последние буквы не могут быть опущены (как в вашем случае, когда буквы являются учащимися), есть две возможности генерировать ровно n/k подмножеств каждую неделю:

• Найдите набор простых чисел p ₁, p ₂, p ₃,... который суммирует до точности п/к. Тогда мы можем рассматривать каждую группу p _i k букв как независимый алфавит, так что вместо нахождения подмножеств pk-букв мы найдем одну группу подмножеств для p ₁ * k букв, другая группа подмножеств для p ₂ * 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 ₁= 113, p ₂= 137 (так что p ₁ + p ₂= 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 или что-то для его просмотра.

Ответ 3

Вот несколько схем алгоритма.

• Сначала найдите все пары: AB BC CD DE EF FG GH HI AC BD CE DF EG FH GI AD BE CF DG EH FI AE BF CG DH EI AF BG CH DI AG BH CI AH BI AI

Они могут быть сохранены в массиве из шестиe n (n-1)

2. Теперь начните попытку комбинировать последовательные пары, используя следующие правила: а. Две пары можно комбинировать только при наличии общего символа. б. Комбинация возможна, когда пара, сформированная путем оставления общего символа, также доступна. например если мы хотим объединить AB и AC, тогда нам нужно проверить, доступен ли BC. с. Когда выполняются вышеприведенные правила, мы объединяем две пары в тройку (например, AB и AC, объединенные для формирования ABC) и отмечаем все три пары, такие как AB, AC и BC, как недоступные.

3. Продолжайте поиск доступных пар в массиве и объедините их, чтобы сформировать тройки и пометить пары, недоступные до тех пор, пока не будет доступных пар, или больше невозможно создать троек.

Пример: 1. объединить AB + AC → ABC; Mark AB, AC и BC недоступны. 2. объединить AD + AE → AED; Марк AD, AE и DE недоступны. 3. объединить AF + AG → AFG; Mark AF, AG и FG недоступны. ..

Ответ 4

Здесь подход, который удовлетворит требованиям, которые вы указали. Делает ли он то, что вы хотите, я не знаю.

• На большом листе бумаги нарисуйте правильную сетку с не менее чем 250 квадратами.
• Пометьте стороны квадратов буквами вашего алфавита (250 квадратов x 4 стороны == 1000).
• Каждый квадрат определяет одно из ваших подмножеств. Каждый из них имеет одну сторону (т.е. одну букву) только с каждым из (до) 4 соседей. Никакая сторона (т.е. письмо) не разделяется более чем на 2 квадрата (подмножества).

Я оставлю это для вас, чтобы превратить это в рабочий код, но я не думаю, что это должно быть слишком сложно, и оно должно хорошо масштабироваться. Обратите внимание, что он также должен работать для любого другого размера подмножества, вы можете разбивать плоскость на нерегулярные n-уголки для любого n, хотя это может стать затруднительным.

Другой подход, о котором я думал, заключается в следующем:

• На большом листе бумаги нарисуйте N точек, где N - размер вашего алфавита. Назовите каждую точку одной из букв алфавита.
• Подключите любые n точек, где n - размер требуемых подмножеств. Это ваше первое подмножество.
• Выберите одну из уже подключенных точек, соедините ее с (n-1) более несвязанными точками. Это ваш следующий поднабор.
• Повторите шаг 3 до тех пор, пока вы не закончите.

Для этого требуется немного больше бухгалтерского учета, и есть ряд угловых дел, с которыми нужно иметь дело, но опять-таки не слишком сложно кодировать.

EDIT: Легко превратить мой первый подход в форму, которая, очевидно, является алгоритмом на графике. Моделируйте каждое подмножество как node, а каждая буква в алфавите - в качестве ребра. Постройте граф, где каждый node имеет степень n (количество элементов в подмножестве), и каждая буква (край) используется один раз.

Ответ 5

@khuss

Тот же метод может быть обобщен. Но это не линейный алгоритм и может быть экспоненциальным.

Например: если размер подмножества равен 4, мы выбираем две или более пары с 4 уникальными символами.

например. "AB и CD" или "AB, AC и AD", только если выполняются следующие условия:

• Доступны все пары, образованные символами 4-кортежа. например если мы хотим сформировать ABCD с использованием AB, AC и AD, тогда все пары из A, B, C и D, то есть AB, AC, AD, BC, BD, CD, должны быть доступны.
• Если выполнено условие 1, то мы формируем ABCD и отмечаем, что C (4,2) = 6 пар недоступны.

Мы продолжаем, как и раньше, до тех пор, пока не будет сформировано больше 4-х кортежей или больше пар не будет доступно.