Типа про IT(@tipaproit). 🤖 Новая задача вам, со звёздочкой. Предположим, имеется X гетеросексуальных мужчин и X гетеросексуа

🤖 Новая задача вам, со звёздочкой. Предположим, имеется X гетеросексуальных мужчин и X гетеросексуальных женщин. Как у мужчин, так и у женщин есть свой личный “краш-рейтинг”, отсортированный в порядке предпочтения, от большего к меньшему. Нам нужно их всех успешно переженить таким образом, чтобы создать устойчивые пары. Например:

guy_preferences = {
    'andrew': ['caroline', 'abigail', 'betty'],
    'bill': ['caroline', 'betty', 'abigail'],
    'chester': ['betty', 'caroline', 'abigail'],
}

gal_preferences = {
    'abigail': ['andrew', 'bill', 'chester'],
    'betty': ['bill', 'andrew', 'chester'],
    'caroline': ['bill', 'chester', 'andrew']
}

Andrew предпочёл бы Caroline, но если не сложится, готов и на Abigail. На худой конец — Betty. У самой Caroline этот наш Andrew на последнем месте, так что скорее всего она остановится на Bill’е. Алгоритм нахождения “устойчивых пар”, он же “алгоритм отложенного согласия”, “stable marriage problem“, “алгоритм Гэйла-Шепли”, в 2012-м отмечен Нобелевской премией по экономике, хотя сам он не нов и был разработан ещё в 1962-м. В русской Википедии всё как-то замуточно описано, но простыми словами происходит следующее. Мужчина идёт по своему списку и каждой зазнобе из него делает предложение. Если зазноба не замужем, она принимает предложение автоматически. Если замужем, она бросает своего нынешнего мужа, как только поступил вариант поинтереснее (ведь у неё тоже есть свой рейтинг). Вот так всё просто и честно, хоть и не все могут быть довольны результатом. Давайте проверим что с этого получится в комментариях. #алкоритмы