Разбить группу из 100 людей по 5, чтобы все перезнакомились?

Question

[Max9999]

Всем добрый день.
Собственно пытаюсь написать алгоритм, чтобы разбивал n людей в группы по 5 человек, чтобы все n перезнакомились друг с другом... Первый круг из пятерок где ни кто не знает ни кого сделал, а вот дальше, как разбивать?

Comments

[Mikhail Osher]

Вопрос непонятен

[Max9999]

Mikhail Osher, Например есть группа 100 человек. Нужно вывести список групп по 5 ч, чтобы все 100 перезнакомились. Получается будет несколько этапов. Первый этап: 1 группа: 1, 2, 3, 4, 5 . 2 группа: 6, 7, 8, 9, 10 ... 20 группа: 96,97,98,99,100. А потом уже пойдут этапы, как миксовать, чтобы меньше повторов было людей, которые уже были в группах друг с другом

[Сергей Соколов]

Кажется, это близко к проблеме школьниц (гуляют по трое, в течение недели должны перегулять каждая с каждой) и social golfer problem (32 игрока, в группе по 4, не оказаться дважды с одним игроком в одной группе)

И на масштабе в 100 «школьниц» и аж 5 за столом, возможно, претендует на Нобелевскую премию (или Дарвина?..)

Answer 1

[Илья]

Как раз для таких ситуаций нужно образование)))) https://ru.wikipedia.org/wiki/Комбинаторика
За основу возьмите https://ru.wikipedia.org/wiki/Сочетание
-
И в постановке наверное пропущено условие типа "за меньшее количество итераций", нет?

Comments

[Max9999]

Да, за меньшее количество итераций.

[Илья]

Если вам нужно само количество - формулы сочетания без повторений.
Если алгоритм, то примерно так:
1. разбиваем N на кучки по 5 (получаем M кучек)
2. далее комбинируем между собой кучки по 10 и получаем новые объединенные (3 человека из первой, 2 человека из второй + 2 человека из первой и 3 из второй), получаем X кучек
3. и так далее (восхождение по дереву поиска от листов к корню)
-
Это все из моего бредового мозга) Неужели алгоритмов нет в гугле?
Ну и надеюсь это не задача со зведочкой, когда можно использовать хаки типа "1 человек из группы перезнакомившихся, может заочно познакомить с другими людьми" :)

[Дмитрий]

Илья,

Ну и надеюсь это не задача со зведочкой,

в текущих реалиях это скорее задачка с вирусом

[uvelichitel]

Илья а где собственно ответ? (Про образование, это вы умнО конечно...)

[Max9999]

Илья, Так не получиться все перебрать((

[Илья]

uvelichitel, не ответ, а подсказка куда копать. Если готовы потратить время на полное расписание алгоритма - велком, мне оно как бы не нужно)
Max9999, почему же? Каждую новую кучку нужно формировать исключительно из незнакомцев. Если просто описать алгоритм словами то:
1. формирует кучки по 5 незнакомцев;
2. если таких кучек нет - то выход, иначе шаг 3
3. знакомим - для каждого человека формируем его круг знакомств (список людей с которыми он знаком)
4. переход к шагу 1

Answer 2

[hint000]

Используйте силу простые числа, как инкремент номеров участников в группе.
5: (1,6,11,16,21), (2,7,12,17,22),..
7: (1,8,15,22,29), (2,9,..),..
11: (1,12,23,34,45), (2,13,..),..
13: ...
17: ...
(плюс зацикливание нумерации: 101=1, 102=2,..)
Доказательство не приведу, пока просто "математическая интуиция".
Оценка снизу: меньше чем за 25 разбиений решения не существует, т.к. каждый должен познакомиться с 99 людьми, а за одно разбиение человек знакомится максимум с 4 людьми, ceil(99/4)=25.