Stable marriage problem in PHP

In computer science there is a problem known as the “stable marriage problem” (SMP). It is a very interesting problem that is best described like this:

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”. – source: Wikipedia

Fortunately, it is already proven that allĀ marriagesĀ can be stable, the proof and the algorithm for such stable marriage problems has been implemented in many languages on rosettacode.org.

Since this blog is about PHP, and this was the language missing from the implementations, I decided to port the Python implementation. So this one is for you:

    $guyprefers = array(
     'abe'  => array('abi', 'eve', 'cath', 'ivy', 'jan', 'dee', 'fay', 'bea', 'hope', 'gay'),
     'bob'  => array('cath', 'hope', 'abi', 'dee', 'eve', 'fay', 'bea', 'jan', 'ivy', 'gay'),
     'col'  => array('hope', 'eve', 'abi', 'dee', 'bea', 'fay', 'ivy', 'gay', 'cath', 'jan'),
     'dan'  => array('ivy', 'fay', 'dee', 'gay', 'hope', 'eve', 'jan', 'bea', 'cath', 'abi'),
     'ed'   => array('jan', 'dee', 'bea', 'cath', 'fay', 'eve', 'abi', 'ivy', 'hope', 'gay'),
     'fred' => array('bea', 'abi', 'dee', 'gay', 'eve', 'ivy', 'cath', 'jan', 'hope', 'fay'),
     'gav'  => array('gay', 'eve', 'ivy', 'bea', 'cath', 'abi', 'dee', 'hope', 'jan', 'fay'),
     'hal'  => array('abi', 'eve', 'hope', 'fay', 'ivy', 'cath', 'jan', 'bea', 'gay', 'dee'),
     'ian'  => array('hope', 'cath', 'dee', 'gay', 'bea', 'abi', 'fay', 'ivy', 'jan', 'eve'),
     'jon'  => array('abi', 'fay', 'jan', 'gay', 'eve', 'bea', 'dee', 'cath', 'ivy', 'hope'));
    $galprefers = array(
     'abi'  => array('bob', 'fred', 'jon', 'gav', 'ian', 'abe', 'dan', 'ed', 'col', 'hal'),
     'bea'  => array('bob', 'abe', 'col', 'fred', 'gav', 'dan', 'ian', 'ed', 'jon', 'hal'),
     'cath' => array('fred', 'bob', 'ed', 'gav', 'hal', 'col', 'ian', 'abe', 'dan', 'jon'),
     'dee'  => array('fred', 'jon', 'col', 'abe', 'ian', 'hal', 'gav', 'dan', 'bob', 'ed'),
     'eve'  => array('jon', 'hal', 'fred', 'dan', 'abe', 'gav', 'col', 'ed', 'ian', 'bob'),
     'fay'  => array('bob', 'abe', 'ed', 'ian', 'jon', 'dan', 'fred', 'gav', 'col', 'hal'),
     'gay'  => array('jon', 'gav', 'hal', 'fred', 'bob', 'abe', 'col', 'ed', 'dan', 'ian'),
     'hope' => array('gav', 'jon', 'bob', 'abe', 'ian', 'dan', 'hal', 'ed', 'col', 'fred'),
     'ivy'  => array('ian', 'col', 'hal', 'gav', 'fred', 'bob', 'abe', 'ed', 'jon', 'dan'),
     'jan'  => array('ed', 'hal', 'gav', 'abe', 'bob', 'jon', 'col', 'ian', 'fred', 'dan'));

    function check($engaged)
    {
        global $guyprefers, $galprefers;
        $inverseengaged = array_combine(array_values($engaged),array_keys($engaged));
        foreach ($engaged as $she => $he)
        {
            $shelikes = $galprefers[$she];
            $shelikesbetter = array_slice($shelikes,0,array_search($he,$shelikes));
            $helikes = $guyprefers[$he];
            $helikesbetter = array_slice($helikes,0,array_search($she,$helikes));

            foreach ($shelikesbetter as $guy)
            {
                $guysgirl = $inverseengaged[$guy];
                $guylikes = $guyprefers[$guy];
                if (array_search($guysgirl,$guylikes) > array_search($she,$guylikes))
                {
                    printf("%s and %s like each other better than ".
                           "their present partners: %s and %s, respectively\n",
                           $she, $guy, $he, $guysgirl);
                    return false;
                }
            }
            foreach ($helikesbetter as $gal)
            {
                $girlsguy = $engaged[$gal];
                $gallikes = $galprefers[$gal];
                if (array_search($girlsguy,$gallikes) > array_search($he,$gallikes))
                {
                    printf("%s and %s like each other better than ".
                           "their present partners: %s and %s, respectively\n",
                           $he, $gal, $she, $girlsguy);
                    return false;
                }
            }
        }
        return true;
    }

    function matchmaker($engaged)
    {
        global $guyprefers, $galprefers;

        $guys = array_keys($guyprefers);
        sort($guys);
        $gals = array_keys($galprefers);
        sort($gals);

        $guysfree = $guys;
        $engaged  = array();
        $guyprefers2 = json_decode(json_encode($guyprefers),true);
        $galprefers2 = json_decode(json_encode($galprefers),true);

        while (count($guysfree))
        {
            $guy = array_shift($guysfree);
            $guyslist = &$guyprefers2[$guy];
            $gal = array_shift($guyslist);
            $fiance = isset($engaged[$gal])?$engaged[$gal]:false;
            if (!$fiance)
            {
                // She's free
                $engaged[$gal] = $guy;
                printf("- %s and %s\n", $guy, $gal);
            }
            else
            {
                // The bounder proposes to an engaged lass!
                $galslist = $galprefers2[$gal];
                if (array_search($fiance,$galslist) > array_search($guy,$galslist))
                {
                    // She prefers new guy
                    $engaged[$gal] = $guy;
                    printf("- %s dumped %s for %s\n", $gal, $fiance, $guy);
                    if ($guyprefers2[$fiance])
                    {
                        // Ex has more girls to try
                        $guysfree[] = $fiance;
                    }
                }
                else
                {
                    // She is faithful to old fiance
                    if (count($guyslist))
                    {
                        // Look again
                        $guysfree[] = $guy;
                    }
                }
            }

        }

        return $engaged;
    }

    $engaged  = array();
    print("Engagements:\n");
    $engaged = matchmaker($engaged);

    print("Couples:\n");
    ksort($engaged);
    foreach ($engaged as $guy => $gal)
    {
        printf("- %s is engaged to %s\n", $guy, $gal);
    }
    $success = check($engaged);
    print("Engagement stability check ".($success?'PASSED':'FAILED')."\n");

    print("Swapping two fiances to introduce an error\n");
    $gals = array_keys($galprefers);
    ksort($gals);
    list($engaged[$gals[0]], $engaged[$gals[1]]) = array($engaged[$gals[1]], $engaged[$gals[0]]);
    print("Couples:\n");
    ksort($engaged);
    foreach ($engaged as $guy => $gal)
    {
        printf("- %s is engaged to %s\n", $guy, $gal);
    }
    print("Engagement stability check ".(check($engaged)?'PASSED':'FAILED')."\n");

Expected output:

Engagements:
- abe and abi
- bob and cath
- col and hope
- dan and ivy
- ed and jan
- fred and bea
- gav and gay
- hope dumped col for ian
- abi dumped abe for jon
- hal and eve
- col and dee
- ivy dumped dan for abe
- dan and fay
Couples:
- abi is engaged to jon
- bea is engaged to fred
- cath is engaged to bob
- dee is engaged to col
- eve is engaged to hal
- fay is engaged to dan
- gay is engaged to gav
- hope is engaged to ian
- ivy is engaged to abe
- jan is engaged to ed
Engagement stability check PASSED
Swapping two fiances to introduce an error
Couples:
- abi is engaged to fred
- bea is engaged to jon
- cath is engaged to bob
- dee is engaged to col
- eve is engaged to hal
- fay is engaged to dan
- gay is engaged to gav
- hope is engaged to ian
- ivy is engaged to abe
- jan is engaged to ed
fred and bea like each other better than their present partners: abi and jon, respectively
Engagement stability check FAILED
Share

Leave a Reply

Your email address will not be published. Required fields are marked *