Вечков Александр, Не понятно. Вам важно, чтобы каждый с каждым поработал одинаковое количество раз? Вы про это ничего ни разу не написали. Даже без добавления всех размещений - все выполняют одинаковое количество всех работ и максимально равномерно по времени.
Alexandroppolus, А если N и M не взаимно просты, то можно разбить всех людей на GCD(N,M) групп одинакового размера, сгенерировать расписание для каждой группы и перемешать их равномерно (сначала первые элементы всех расписаний, потом вторые, потом третьи в том же порядке и т.д.)
Вечков Александр, А много у вас людей/занятий?
Обязательно ли вам все комбинации использовать? Например, из 4 человек с 2 занятиями можно сделать:
[[1,2], [3,4], [2,1], [4,3]]. Тут и повторов минимальное количество и все люди одинаково часто делают все занятия. Или вам обязательно надо еще [1,3], [3,1], [2,4], [4,2],[2,3],[3,2],[4,1],[1,4] куда-то добавить?
AlexNew22, Вместо среднего вычисляется сумма в скользящем окне. Среднее же вычисляется как сумма, деленная на количество чисел в окне. Для пересчета суммы при сдвиге окна надо лишь добавить одно новое число справа и убрать отдно старое число слева.
Jacen11, Наидлиннейший путь почти наверняка загонит змейку в тупик по спирали вокруг конечной точки.
Это очень хитрая задача, скорее всего на паттерны. Тривиальное решение - гонять змейку по кольцевому маршруту вдоль всего поля. Так, змейка будет обходить все клектки поля по одному разу за круг. Рано или поздно она съест яблоко и сможет двигаться так пока не заполнит все поле.
Но это вообще не интересное поведение. Интересно было бы найти кратчайший маршрут такой, что все свободные клетки поля все еще оказываются доступны. Но это тоже очень сложная задача - тут нужен перебор какой-то.
mayton2019, Да, этот метод требует сделать максимум один лишний круг по циклу. Но в задаче и так надо все состояния до зацикливания сгенерировать (Т.е. все 1 257 665 051). Так что один лишний круг не сильно все портит.
mayton2019, потому что 2-1=1. За каждую итерацию расстояние между двумя состояниями будет изменятся на 1. Ну и это же количество шагов - так что число должно быть целым.
По поводу идеи автора с удвоением времени. Может не сработать если период повтора не будет кратен двойке.
Нет. Сработает всегда. Основное поле двигается на 1 ход, вспомогательное - на 2. Вспомогательное обгоняет основное на 1 шаг за каждую итерацию. Через 2 итерации - будет 2 шага. Через K - K шагов. Рано или поздно расстояние между двумя полями (в смысле шагов) станет равно периоду.
Василий Банников, Нет, это так не работает. Некоторые алгоритмы, измененные таким образом - просто повиснут навсегда. Другие могут найти какой-то случайный путь, или вообще обломаться после первой же итерации и не найти ничего.
Adamos, Нет, все-таки, в питоне. сортировка даже массива из единиц не может быть быстрее тупо цикла (на том же уровне абстрации). Просто вот оказалось, что даже сортировка на си быстрее прохода по списку в питоне.
Однако, как и стоило ожидать, линейный перебор на си - оказался в несколько раз быстрее сортировки ( Wispik выше привел замеры - count самый быстрый).
Wispik, А sum или filter какой-нибудь тогда не будет еще быстрее? Должна же быть какая-то линейная проверка всех элементов массива, реализованная на Си.
В третьем комменте вы написали.
Это не то, о чем я справшиваю. Это ваше требование вот этим решением покрыто: [[1,2], [3,4], [2,1], [4,3]]. Но тут 1 никогда не работает с 3.
Важно ли вам, что бы каждая пара людей вместе поработала? Это не о честности и равенстве, это отдельное требование само в себе.