C++ प्रोग्राम: Stable Marriage Problem (Gale-Shapley Algorithm)

यह C++ प्रोग्राम Stable Marriage Problem (स्थिर विवाह समस्या) को हल करता है जिसे Gale-Shapley Algorithm से भी जाना जाता है। N पुरुष और N महिलाएं दी गई हैं, प्रत्येक ने विपरीत लिंग के सभी सदस्यों को वरीयता क्रम में रैंक किया है। लक्ष्य यह है कि उन्हें इस तरह जोड़ा जाए कि कोई भी दो विपरीत लिंग के व्यक्ति अपने वर्तमान पार्टनर के बजाय एक-दूसरे को प्राथमिकता न दें।

एल्गोरिदम

शुरुआत
  1. फंक्शन WomenPrefersMenOverMen1():
     - जांचें कि महिला अपने वर्तमान मंगेतर (men1) के बजाय नए पुरुष (men) को प्राथमिकता देती है या नहीं
     - यदि men1, men से पहले महिला की सूची में आता है, तो वह वर्तमान मंगेतर को प्राथमिकता देती है
     - यदि men, men1 से पहले आता है, तो वर्तमान सगाई तोड़ें और men से सगाई करें
  
  2. फंक्शन stableWedding():
     - पुरुषों को 0 से N-1 तक नंबर दें
     - महिलाओं को N से 2N-1 तक नंबर दें
     - जब तक पुरुष मुक्त हैं:
         A) पहला मुक्त पुरुष चुनें
         B) उसकी वरीयता के अनुसार एक-एक करके सभी महिलाओं के पास जाएं
         C) यदि पसंद की महिला मुक्त है, तो वे पार्टनर बन जाते हैं
         D) यदि महिला मुक्त नहीं है, तो उसके वर्तमान मंगेतर को खोजें
         E) यदि महिला नए पुरुष को अपने वर्तमान मंगेतर से अधिक पसंद करती है,
            तो वर्तमान सगाई तोड़ें और नए पुरुष से सगाई करें
समाप्ति

उदाहरण कोड

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

#define N 4

bool womanPrefersManOverMan1(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;  // नए पुरुष को प्राथमिकता
    }
    return true;
}

void stableMarriage(int prefer[2*N][N]) {
    int wPartner[N];  // महिलाओं के पार्टनर स्टोर करने के लिए
    bool mFree[N];    // पुरुषों की उपलब्धता स्टोर करने के लिए
    
    memset(wPartner, -1, sizeof(wPartner));
    memset(mFree, false, sizeof(mFree));
    
    int freeCount = N;
    
    while (freeCount > 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;
                freeCount--;
            }
            // यदि महिला मुक्त नहीं है
            else {
                int m1 = wPartner[w - N];
                // यदि महिला नए पुरुष को वर्तमान से अधिक पसंद करती है
                if (!womanPrefersManOverMan1(prefer, w, m, m1)) {
                    wPartner[w - N] = m;
                    mFree[m] = true;
                    mFree[m1] = false;
                }
            }
        }
    }
    
    cout << "Woman\tMan\n";
    for (int i = 0; i < N; i++)
        cout << " " << i + N << "\t" << wPartner[i] << endl;
}

int main() {
    int prefer[2*N][N] = {
        {7, 5, 6, 4},  // महिला 4 की वरीयता
        {5, 4, 7, 6},  // महिला 5 की वरीयता
        {4, 5, 7, 6},  // महिला 6 की वरीयता
        {4, 5, 7, 6},  // महिला 7 की वरीयता
        {0, 1, 3, 2},  // पुरुष 0 की वरीयता
        {0, 1, 3, 2},  // पुरुष 1 की वरीयता
        {0, 1, 3, 2},  // पुरुष 2 की वरीयता
        {0, 1, 3, 2}   // पुरुष 3 की वरीयता
    };
    
    stableMarriage(prefer);
    return 0;
}

आउटपुट

Woman Man
4       3
5       1
6       2
7       0

महत्वपूर्ण बिंदु: यह एल्गोरिदम पुरुष-इष्टतम (male-optimal) स्थिर मिलान देता है। समय जटिलता O(N²) है। यह एल्गोरिदम वास्तविक दुनिया में रेजिडेंसी मिलान, स्कूल चयन आदि में उपयोग होता है।