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

Question

[Боб Семович]

У меня есть массив [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 цифр в массиве) . Суть в том что бы составить такой график уборки в котором одни и те же люди не будут убираться несколько дней подряд и будут равномерно распределены на месяц.

Comments

[Сергей Сергей]

смещать все три позиции, например:

1, 2, 3
4, 5, 6
7, 1, 2
3, 4, 5
6, 7, 1

[Wataru]

У вас там три разных дежурства? Почему в массиве есть [1,2,3] и [1,3,2]?

[Боб Семович]

Wataru,
Это важный момент. Каждый из троих выполняет разную работу и нужно что бы каждый из них побывал на разном виде работ. Я использовал размещение, а не сочетание как раз для этого

[Боб Семович]

Сергей Сергей, не пойдёт. А если цифр в массиве 9? Тогда через 3 комбинации, комбинации будут повторяться. А я использую не сочетание а размещение (термины из комбинаторики).
Т.е. мне важно что бы были комбинация не только 1,2,3, но и 1,3,2, и 2,1,3 и т.д.

[Сергей Сергей]

Каждую позицию смещать по-разному, учитывая совпадения элементов. Ищи на хабре "принцип цикад".

[Wataru]

Вечков Александр, А много у вас людей/занятий?
Обязательно ли вам все комбинации использовать? Например, из 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] куда-то добавить?

[Боб Семович]

Wataru, Да. обязательно. Выше в комментарии я написал почему

[Wataru]

Вечков Александр, Не понятно. Вам важно, чтобы каждый с каждым поработал одинаковое количество раз? Вы про это ничего ни разу не написали. Даже без добавления всех размещений - все выполняют одинаковое количество всех работ и максимально равномерно по времени.

[Боб Семович]

Сергей Сергей, Спасибо, на хабре посмотрел, но это не подходит потому что принцип цикад подразумевает почти рандом. А мне нужно равномерное распределение цифр. Допускаю, что я что-то не понял

[Боб Семович]

Wataru, 3 комментарий к моему вопросу

[Сергей Сергей]

Ну да, псевдорандом. Для контроля равномерности можно как-то "играться" длиной — частотой выпадания элемента.

[Wataru]

Вечков Александр,

3 комментарий к моему вопросу

В третьем комменте вы написали.

Каждый из троих выполняет разную работу и нужно что бы каждый из них побывал на разном виде работ.

Это не то, о чем я справшиваю. Это ваше требование вот этим решением покрыто: [[1,2], [3,4], [2,1], [4,3]]. Но тут 1 никогда не работает с 3.

Важно ли вам, что бы каждая пара людей вместе поработала? Это не о честности и равенстве, это отдельное требование само в себе.

Answer 1

[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

Answer 2

[Alexandroppolus]

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

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

Comments

[Боб Семович]

спасибо за идею. Где почитать/посмотреть про это(хеш таблицы и проверку на то где меньше всего дежурств)?

[Alexandroppolus]

хэш-таблица - обычный Map.
Хотя щас думаю, тут он не нужен, а нужна двоичная куча. Её нет в js из коробки, но пилится на раз-два, или можно взять готовую. В ней надо будет держать объекты {user, count}, где count - количество дежурств, и сравнивать по count.

Правда, из комментов я понял, что все дежурства разные, и понадобится отдельная куча на каждый вид дежурства. Из каждой кучи выбираешь по одному юзеру. Но если из первой кучи ты выбрал, например, user=5, а во второй куче тоже он сверху, то придется его из второй удалить, выбрать другого, и вернуть удаленного. Навскидку так, немного костыльно.

[Alexandroppolus]

хотя можно и проще. Что-то я переусложнил, как водится.
например, массив из M челов: 1, 2, 3, 4, 5, 6, 7
выбираешь N чел., просто бегая по кругу:
1, 2. 3
4, 5, 6
7, 1, 2
3, 4, 5
...
Если N и M взаимно простые, то всё идеально: наборы будут сдвигаться, чуваки - попадать на разные работы. Иначе придется наборы как-то перетасовывать

[Wataru]

Alexandroppolus, А если N и M не взаимно просты, то можно разбить всех людей на GCD(N,M) групп одинакового размера, сгенерировать расписание для каждой группы и перемешать их равномерно (сначала первые элементы всех расписаний, потом вторые, потом третьи в том же порядке и т.д.)