Задача о марьяже (о стабильных браках)

Как контейнеры не делают наш код легче и понятней :)

Постановка задачи есть в "Вики", там же - решение на классическом Си. Наше решение получилось несколько более громоздким, зато на стандартных контейнерах STL и с именами вместо индексов.

Предполагается, что мощности множеств одинаковы, то есть, пары можно образовать в любом случае, корректность заполнения исходных данных men_data и women_data не контролируется. Зато код в таком виде должен нормально обобщаться на неравное количество партнёров, думается.

Консольное приложение C++ проверялось в актуальной сборке Visual Studio 2019, далее приводится полный листинг и копия вывода в консоль.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

typedef std::vector<std::string> PrefList;
typedef std::map<std::string, PrefList> PrefMap;
typedef std::map<std::string, std::string> Couples;

bool prefers(const PrefList& prefer, const std::string& first, const std::string& second) {
 // Появляется ли «первый» перед «вторым» в списке предпочтений?
 for (PrefList::const_iterator it = prefer.begin(); it != prefer.end(); ++it) {
  if (*it == first) return true;
  if (*it == second) return false;
 }
 return false;
}

void check_stability(const Couples& engaged, const PrefMap& men_pref, const PrefMap& women_pref) {
 std::cout << "Stablility:" << std::endl;
 bool stable = true;
 for (Couples::const_iterator it = engaged.begin(); it != engaged.end(); ++it) {
  const std::string& bride = it->first;
  const std::string& groom = it->second;
  const PrefList& preflist = men_pref.at(groom);
  for (PrefList::const_iterator it = preflist.begin(); it != preflist.end(); ++it) {
   if (*it == bride) break; // он предпочитает свою невесту
   if (prefers(preflist, *it, bride) && // он предпочитает другую женщину
    prefers(women_pref.at(*it), groom, engaged.at(*it))) { // другая женщина предпочитает его
    std::cout << "\t" << *it <<
     " prefers " << groom <<
     " over " << engaged.at(*it) <<
     " and " << groom <<
     " prefers " << *it <<
     " over " << bride << std::endl;
    stable = false;
   }
  }
 }
 if (stable) std::cout << "\t(all marriages stable)" << std::endl;
}

//Исходные данные
const int N = 5;
const char* men_data[][N + 1] = {
 { "Corwin", "Basya","Avka","Delta","Murka","Fifi" },
 { "Dunduk", "Delta","Basya","Avka","Fifi","Murka" },
 { "Tema",   "Avka","Basya","Fifi","Murka","Delta" },
 { "Baran",  "Fifi","Delta","Murka","Basya","Avka" },
 { "Sidor",  "Basya","Fifi","Delta","Murka","Avka" }
};

const char* women_data[][N + 1] = {
 { "Avka", "Dunduk","Corwin","Baran","Sidor","Tema" },
 { "Basya", "Corwin","Dunduk","Sidor","Baran","Tema" },
 { "Delta", "Tema","Baran","Sidor","Dunduk","Corwin" },
 { "Fifi", "Sidor","Dunduk","Corwin","Tema","Baran" },
 { "Murka", "Baran","Tema","Corwin","Sidor","Dunduk" }
};

int main() {
 PrefMap men_pref, women_pref;
 std::queue<std::string> bachelors;
 for (int i = 0; i < N; ++i) { // люди
  for (int j = 1; j < N + 1; ++j) { // предпочтения
   men_pref[men_data[i][0]].push_back(men_data[i][j]);
   women_pref[women_data[i][0]].push_back(women_data[i][j]);
  }
  bachelors.push(men_data[i][0]);
 }
 Couples engaged; // <Ж,М>
 std::cout << "Tests:" << std::endl;
 while (!bachelors.empty()) {
  const std::string& suitor = bachelors.front();
  const PrefList& preflist = men_pref[suitor];
  for (PrefList::const_iterator it = preflist.begin(); it != preflist.end(); ++it) {
   const std::string& bride = *it;
   if (engaged.find(bride) == engaged.end()) { // она доступна
    std::cout << "\t" << bride << " & " << suitor << std::endl;
    engaged[bride] = suitor; // соединить
    break;
   }
   const std::string& groom = engaged[bride];
   if (prefers(women_pref[bride], suitor, groom)) {
    std::cout << "\t" << bride << " poslala " << groom << " radi " << suitor << std::endl;
    bachelors.push(groom); // сбросить этот вариант
    engaged[bride] = suitor; 
    break;
   }
  }
  bachelors.pop();
 }
 std::cout << "Couples:" << std::endl;
 for (Couples::const_iterator it = engaged.begin(); it != engaged.end(); ++it) {
  std::cout << "\t" << it->first << " & " << it->second << std::endl;
 }
 check_stability(engaged, men_pref, women_pref);

 //Две дуры поменялись мужиками:
 std::cout << "Perturbation:" << std::endl;
 std::swap(engaged["Avka"], engaged["Basya"]);
 std::cout << "\tengage Avka with " << engaged["Avka"] << " and Basya with " << engaged["Basya"] << std::endl;
 check_stability(engaged, men_pref, women_pref);
 return 0;
}

Tests:
        Basya & Corwin
        Delta & Dunduk
        Avka & Tema
        Fifi & Baran
        Fifi poslala Baran radi Sidor
        Delta poslala Dunduk radi Baran
        Avka poslala Tema radi Dunduk
        Murka & Tema
Couples:
        Avka & Dunduk
        Basya & Corwin
        Delta & Baran
        Fifi & Sidor
        Murka & Tema
Stablility:
        (all marriages stable)
Perturbation:
        engage Avka with Corwin and Basya with Dunduk
Stablility:
        Basya prefers Corwin over Dunduk and Corwin prefers Basya over Avka

13.06.2022, 23:37 [743 просмотра]