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

Question

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

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

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

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

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

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

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

Answer 1

Теория: у вас есть двудольный граф .Вы должны найти Идеальное совпадение .Существует идеальное соответствие на графике, если:

• | A |= | B |
• График удовлетворяет условию Холла

Если существует идеальное соответствие, вы можете запустить Венгерский алгоритм длянайди это.

Answer 2

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