Как в js равномерно распределить комбинации пунктов в массиве, который был создан с помощью рекурсивного размещения?

У меня есть массив [1,2,3,4,5,6,7...] мне нужно было получить список всех комбинаций состоящих из N количества последовательностей (рекурсивное размещение).
в итоге я получил такой массив:
[ [ 1, 2, 3 ],
  [ 1, 2, 4 ],
  [ 1, 2, 5 ],
  [ 1, 2, 6 ],
  [ 1, 2, 7 ],
  [ 1, 3, 2 ],
  [ 1, 3, 4 ],
  [ 1, 3, 5 ],
  [ 1, 3, 6 ],
  [ 1, 3, 7 ],
  [ 1, 4, 2 ],
  [ 1, 4, 3 ],
  [ 1, 4, 5 ],
  [ 1, 4, 6 ],
  [ 1, 4, 7 ],
  [ 1, 5, 2 ],
  [ 1, 5, 3 ],
  [ 1, 5, 4 ],
  [ 1, 5, 6 ],
  [ 1, 5, 7 ],
  [ 1, 6, 2 ],
  [ 1, 6, 3 ],
  [ 1, 6, 4 ],
  [ 1, 6, 5 ],
  [ 1, 6, 7 ],
  [ 1, 7, 2 ],
  [ 1, 7, 3 ],
  [ 1, 7, 4 ],
  [ 1, 7, 5 ],
  [ 1, 7, 6 ],
  [ 2, 1, 3 ],
  [ 2, 1, 4 ],
  [ 2, 1, 5 ],
  [ 2, 1, 6 ],
  [ 2, 1, 7 ],
  ...
  ]


Как мне распределить комбинации этого массива так, что бы цифры каждой комбинации максимально редко повторялись в последующих комбинациях массива?

Что бы было понятнее расскажу для чего мне это нужно: каждая цифра представляет отдельного человека. Есть график уборки (каждый день убирается 3 человека - они представлены комбинацией из 3 цифр в массиве) . Суть в том что бы составить такой график уборки в котором одни и те же люди не будут убираться несколько дней подряд и будут равномерно распределены на месяц.
  • Вопрос задан
  • 168 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Если вам не надо чтобы каждый человек одинаково часто работал с каждым другим, то подойдет обощение решения, предложенного в комментариях Alexandroppolus и Сергей Сергей.

Допустим количество работ (N) и количество людей (M) взаимно просты.

Тогда сгенерируйте M строчек беря людей подряд:
1, 2, 3
4, 5, 1
2, 3, 4
5, 1, 2
3, 4, 5

Тут каждый человек одинаковое количество раз (по одному разу) будет на каждой работе. И дни, когда он будет работать будут максимально равномерно распределены (минимальное расстояние и максимальное между соседними работами будут различаться максимум на 1 и равны floor(N/M) и ceil(N/M)). Это идеальное с точки зрения равенства расписание. Но у него минус - частоты пар работников будут не одинаковыми. 1 гораздо чаще будет работать с 2 и 5, чем с 3 и 4.

Теперь, если N и M не взяимно просты. Пусть D = GCD(N,M) - наибольший общий делитель.

Разбейте всех людей на D групп по N'=N/D человек. N' и M взяимно просты, поэтому можно применить алгоритм выше к каждой группе.

Дальше эти D расписаний надо перемешать. Для максимальной равномерности - сначала взять все первые строки всех расписаний, потом все вторые, и т.д.

На i-ом месте будет день i / N' из расписания i % N' (если индексация с 0).

Так, например, решение для 2 работ и 6 людей:

N' = 3. 2 группы.
В первой:
1 2
3 1
2 3

Во второй:
4 5
6 4
5 6

В итоге:
1 2
4 5
3 1
6 4
2 3
5 6
Ответ написан
Комментировать
Alexandroppolus
@Alexandroppolus
кодир
заведи массив или хэштаблицу - кто сколько раз дежурил, изначально у всех нули.
на каждый очередной день выбирай N челиков, у которых меньше всего дежурств.
если там здоровенное количество сотрудников, то для быстрого поиска самых малодежурных поможет приоритетная очередь, например на основе бинарной кучи.

заодно не придется возиться с размещениями, вариант получается более простой.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы