C++ প্রোগ্রাম: স্টেবল ম্যাচিং সমস্যা সমাধান (নির্দিষ্ট কেস)

এটি একটি C++ প্রোগ্রাম যা একটি নির্দিষ্ট কেসের জন্য ম্যাচিং সমস্যা সমাধান করে। এখানে N পুরুষ এবং N মহিলা দেওয়া আছে, প্রতিটি ব্যক্তি বিপরীত লিঙ্গের সব সদস্যকে পছন্দের ক্রমে র‍্যাঙ্ক করে। পুরুষ ও মহিলাকে বিবাহ বন্ধনে বাঁধা হবে এমনভাবে যাতে দুজন বিপরীত লিঙ্গের ব্যক্তি না থাকে যারা একে অপরের পক্ষে তাদের বর্তমান পার্টনার চেয়ে বেশি পছন্দ করব। সব বিবাহ "স্টেবল" হবে যদি এমন কোনো লোক না থাকে।

অ্যালগরিদম

শুরু
  ফাংশন WomenPrefersMenOverMen1():
    A) চেক করুন মহিলা পুরুষকে তার বর্তমান এনগেজমেন্ট men1 চেয়ে বেশি পছন্দ করে কিনা
    B) যদি মহিলার লিস্টে men1, men-এর আগে থাকে, তবে মহিলা তার বর্তমান এনগেজমেন্ট পছন্দ করে।
    C) যদি মহিলার লিস্টে men, men1-এর আগে থাকে, তবে তার বর্তমান এনগেজমেন্ট ভাঙুন এবং তাকে men-এর সাথে এনগেজ করুন।
শেষ
শুরু
  ফাংশন stablewedding():
    1) পুরুষরা ০ থেকে N-1 পর্যন্ত নম্বর দিয়ে চিহ্নিত।
    2) মহিলারা N থেকে 2N-1 পর্যন্ত নম্বর দিয়ে চিহ্নিত।
    3) যতক্ষণ পুরুষরা ফ্রি থাকে
       A) প্রথম ফ্রি পুরুষকে পিক করুন
       B) পিক করা ফ্রি পুরুষের পছন্দ অনুযায়ী একে একে সব মহিলার কাছে যান।
       C) পছন্দের মহিলা ফ্রি থাকলে, মহিলা এবং পুরুষ партনার হয়।
       D) যদি মহিলা ফ্রি না থাকে, মহিলার বর্তমান এনগেজমেন্ট খুঁজুন
       E) যদি মহিলা পুরুষকে তার বর্তমান এনগেজমেন্ট men1 চেয়ে পছন্দ করে, তবে মহিলা এবং men1-এর এনগেজমেন্ট ভাঙুন এবং পুরুষকে মহিলার সাথে এনগেজ করুন।
শেষ

উদাহরণ

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 4

bool WomenPrefersMenOverMen1(int prefer[2*N][N], int w, int m, int m1) {
    for (int i = 0; i < N; i++) {
        if (prefer[w][i] == m1)
            return true;
        if (prefer[w][i] == m)
            return false;
    }
}

void stablewedding(int prefer[2*N][N]) {
    int wPartner[N]; // মহিলাদের পার্টনার স্টোর করার অ্যারে
    bool mFree[N];   // পুরুষদের উপলব্ধতা স্টোর করার অ্যারে
    // সব পুরুষ ও মহিলাকে ফ্রি হিসেবে ইনিশিয়ালাইজ করুন
    memset(wPartner, -1, sizeof(wPartner));
    memset(mFree, false, sizeof(mFree));
    int freeCnt = N;
    while (freeCnt > 0) { // যতক্ষণ পুরুষ ফ্রি থাকে
        int m; // প্রথম ফ্রি পুরুষ পিক করুন
        // পিক করা ফ্রি পুরুষের পছন্দ অনুযায়ী একে একে সব মহিলার কাছে যান।
        for (m = 0; m < N; m++)
            if (mFree[m] == false)
                break;
        for (int i = 0; i < N && mFree[m] == false; i++) {
            int w = prefer[m][i];
            // পছন্দের মহিলা ফ্রি থাকলে, মহিলা ও পুরুষ партনার হয়।
            if (wPartner[w-N] == -1) {
                wPartner[w-N] = m;
                mFree[m] = true;
                freeCnt--;
            } else { // যদি মহিলা ফ্রি না থাকে
                // মহিলার বর্তমান এনগেজমেন্ট খুঁজুন
                int m1 = wPartner[w-N];
                // যদি মহিলা পুরুষকে তার বর্তমান এনগেজমেন্ট men1 চেয়ে পছন্দ করে,
                // তবে মহিলা ও men1-এর এনগেজমেন্ট ভাঙুন এবং পুরুষকে মহিলার সাথে এনগেজ করুন।
                if (WomenPrefersMenOverMen1(prefer, w, m, m1) == false) {
                    wPartner[w-N] = m;
                    mFree[m] = true;
                    mFree[m1] = false;
                }
            }
        }
    }
    cout << "Woman Man" << endl;
    for (int i = 0; i < N; i++)
        cout << " " << i+N << "\t" << wPartner[i] << endl;
}

int main() {
    int p[2*N][N] = {
        {7, 5, 6, 4},
        {5, 4, 7, 6},
        {4, 5, 7, 6},
        {4, 5, 7, 6},
        {0, 1, 3, 2},
        {0, 1, 3, 2},
        {0, 1, 3, 2},
        {0, 1, 3, 2},
    };
    stablewedding(p);
    return 0;
}

আউটপুট

Woman Man 4 3 5 1 6 2 7 0