Алгоритм равномерного распределения лотереи «призы»/без дисперсии

Question

Моя проблема: я хочу сделать «добрый» лотерейный процесс. Этот алгоритм будет распределять призы равномерно, если это возможно. Это можно считать несправедливым для людей, которые покупают билет на каждый приз, поскольку он будет более гибким, чтобы выиграть непопулярные призы, но неважно, что мы можем сказать, что призы примерно одинаковы. Алгоритм поможет убить дисперсию и уменьшить дисеролинг, чтобы выиграть призы. (Да, расточка)

У меня будет N конкурсов, Вы могли бы получить приз. Лица, M, могут купить билет на каждые N.

Так пример, вот призы и люди, которые купили билеты:

Prize1=[Pete,Kim, Jim] 
Prize2=[Jim, Kim] 
Prize3=[Roger, Kim] 
Prize4=[Jim] 

Там 4 призы и 4 уникальных имен, поэтому оно должно быть возможным распределить его равномерно.

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

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

Answer 1

Вы хотите найти алгоритм задания или венгерский алгоритм, например, взвешенное идеальное совпадение в двудольном графе или, возможно, алгоритм all-pair floyd warshall. Моя идея состоит в том, что это может представлять собой двудольный граф. Это непростая задача.

Answer 2

Теория: У вас есть Bipartite graph. Вы должны найти Perfect matching. Существует идеальное соответствие на графике, если:

• | A | = | B |
• Граф удовлетворяет Hall condition

Если совершенное паросочетание существует, то вы можете запустить Hungarian algorithm, чтобы найти его.