Stable marriage problem: Difference between revisions

# [http://www.ams.org/samplings/feature-column/fc-2015-03 The Stable Marriage Problem and School Choice]. (Excellent exposition)

<br><br>

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey L}}

abe := ["abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"]

bob := ["cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"]

Else

Return "`nThese couples are stable.`n"

{{out}}

<pre>Engagements:

 

=={{header|Batch File}}==

setlocal enabledelayedexpansion

 

 

 

 

call :stableMatching

call :display

call :isStable

call :swapper ed hal

call :display

call :isStable

pause>nul

exit /b 0

 

:stableMatching

 

 

 

:display

goto :EOF

 

:isStable

)

goto :EOF

 

:swapper

{{Out}}

<pre>HISTORY:

 

NEWLYWEDS:

 

STABILITY = TRUE.

 

NEW-NEWLYWEDS:

 

STABILITY = FALSE.

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

DIM mname$(N), wname$(N), mpref$(N), wpref$(N), mpartner%(N), wpartner%(N)

DIM proposed&(N,N)

NEXT o%

NEXT m%

'''Output:'''

<pre>

 

=={{header|Bracmat}}==

(bob.cath hope abi dee eve fay bea jan ivy gay)

(col.hope eve abi dee bea fay ivy gay cath jan)

| out$stable

)

{{out}}

<pre>stable

=={{header|C}}==

Oddly enough (or maybe it should be that way, only that I don't know): if the women were proposing instead of the men, the resulting pairs are exactly the same.

 

int verbose = 0;

 

return 0;

{{out}}

<pre>Pairing:

Fred (w/ Cath) and Abi (w/ Jon) prefer each other over current pairing.

Marriages not stable</pre>

 

=={{header|C++}}==

#include <iostream>

#include <map>

 

check_stability(engaged, men_pref, women_pref);

{{out}}

<pre>

</pre>

 

 

}

}

}

}

}

}

}

}

{{out}}

 

=={{header|CoffeeScript}}==

constructor: (@name, @preferences) ->

@mate = null

perturb guys

report_on_mates guys

{{out}}

<pre>

 

=={{header|ColdFusion}}==

PERSON.CFC

 

}

}

INDEX.CFM

 

}

</cfscript>

{{out}}

<pre>

Nope, now everything is broken. Sharing spouses doesn't work, kids.

</pre>

=={{header|D}}==

From the Python and Java versions:

 

 

c = check!(true)(engagedTo, guyPrefers, galPrefers);

writeln("Marriages are ", c ? "stable" : "unstable");

{{out}}

<pre>Engagements:

Marriages are unstable</pre>

===Stronger Version===

 

enum F { abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan }

checkStability(engaged, menPref, womenPref);

}

{{out}}

<pre>Matchmaking:

 

=={{header|EchoLisp}}==

(lib 'hash)

;; input data

(error 'not-stable (list man woman)))))

{{out}}

<pre>

 

=={{header|F_Sharp|F#}}==

Map.ofList

["abe", ["abi";"eve";"cath";"ivy";"jan";"dee";"fay";"bea";"hope";"gay"];

husbandOf = solution.husbandOf.Add( gal0, guy1 ).Add( gal1, guy0 ) }

 

{{out}}

<pre>

 

=={{header|Go}}==

 

import "fmt"

fmt.Println("stable.")

return true

{{out}}

<pre>

 

"Stable Matching" Solution:

import static Woman.*

 

}

engagedTo

 

"Stability Checking" Solution:

(Could do more to eliminate common code. Maybe later.)

matches.collect{ girl, guy ->

int guysRank = galsGuyRanking[girl][guy]

true

}.every()

 

Test (Stable and Perturbed):

abe, bob, col, dan, ed, fred, gav, hal, ian, jon

}

println ''

 

{{out}}

<pre>abi (his '10' girl) is engaged to jon (her '8' guy)

 

=={{header|Haskell}}==

 

 

 

 

 

 

 

 

 

 

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

return X

 

{{libheader|Icon Programming Library}}

 

=={{header|J}}==

abe: abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay

bob: cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay

end.

assert-.bad

 

For most of this, males and females are both represented by indices. Rows of <code>Mprefs</code> are indexed by a male index and each contains a list female indices, in priority order. Rows of <code>Fprefs</code> are indexed by a female index and each contains a list male indices in priority order. These indices select the corresponding names from <code>GuyNames</code> and <code>GalNames</code>.

Example use:

 

┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐

│abe│bob │col│dan│ed │fred│gav│hal│ian │jon│

├───┼────┼───┼───┼───┼────┼───┼───┼────┼───┤

│ivy│cath│dee│fay│jan│bea │gay│eve│hope│abi│

 

Stability check:

 

 

(no news is good news)

An altered result, and a stability check on it (showing what would happen for a bogus result):

 

┌───┬────┬───┬───┬───┬────┬───┬───┬────┬───┐

│abe│bob │col│dan│ed │fred│gav│hal│ian │jon│

└────┴───┘

|assertion failure: assert

As an aside, note that the guys fared much better than the gals here, with over half of the guys getting their first preference and only one gal getting her first preference. The worst match for any guy was fourth preference where the worst for any gal was seventh preference.

 

=={{header|Java}}==

This is not a direct translation of [[#Python|Python]], but it's fairly close (especially the stability check).

 

public class Stable {

return true;

}

{{out}}

<pre>abi is engaged to jon

 

=={{header|JavaScript}}==

 

var candidateIndex = 0;

 

doMarriage();

 

{{out}}

Stable = No</pre>

 

 

 

 

 

break

}

}

 

}

 

}

 

}

 

 

 

 

}

}

 

fun main(args: Array<String>) {

 

 

{{out}}

 

=={{header|Lua}}==

{{trans|C#}}

 

Person.__index = Person

 

jon.fiance, fred.fiance = fred.fiance, jon.fiance

print('Stable: ', isStable(men))

 

{{out}}

Stable: false

</pre>

 

=={{header|Objective-C}}==

{{Works with|XCode 4.5.1}}

(The C# version is essentially the same as this.)

// Person class

 

}

return 0;

 

{{out}}

 

=={{header|OCaml}}==

"abe", ["abi";"eve";"cath";"ivy";"jan";"dee";"fay";"bea";"hope";"gay"];

"bob", ["cath";"hope";"abi";"dee";"eve";"fay";"bea";"jan";"ivy";"gay"];

let engagements = perturb_engagements engagements in

print engagements;

{{out}}

<pre> fay is engaged with dan

 

=={{header|Perl}}==

use strict;

use warnings;

 

sub men { keys %{ $Likes{M} } }

{{out}}

<pre>

bea prefers fred to jon and fred prefers bea to abi

</pre>

 

 

 

 

=={{header|PicoLisp}}==

*Boys (list

(de abe abi eve cath ivy jan dee fay bea hope gay)

(con (asoq 'fred *Couples) 'abi)

(con (asoq 'jon *Couples) 'bea)

{{out}}

<pre>dee is engaged to col

gay likes jon better than gav and jon likes gay better than bea

bea likes fred better than jon and fred likes bea better than abi</pre>

 

=={{header|Prolog}}==

{{Works with|SWI-Prolog}}{{libheader|XPCE}}

XPCE is used for its integrated messaging system.

% facts

prefere(abe,[ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay]).

( (IY12 < IY11 , IX21 < IX22);

(IY21 < IY22 , IX12 < IX11)).

{{out}}

<pre> ?- stable_mariage.

true </pre>

A more Prolog-ish version (working with SWI-Prolog) could be :

% person(Name, Preference, Status, Candidate)

% prop(Name, List_of_Candidates) (for a woman)

% A couple is unstable

( (IY12 < IY11 , IX21 < IX22);

 

=={{header|PureBasic}}==

This approach uses a messaging system to pass messages between prospective partners.

 

DataSection

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

{{out}}

<pre>Marriages:

 

=={{header|Python}}==

 

guyprefers = {

print()

print('Engagement stability check PASSED'

{{out}}

<pre>Engagements:

fay and jon like each other better than their present partners: dan and bea, respectively

Engagement stability check FAILED</pre>

 

=={{header|Racket}}==

#lang racket

 

(swap! (hash-ref matches (car M)) (hash-ref matches (cadr M))))

(check-stability)

 

Sample run:

</pre>

 

 

 

Algorithm used: see link https://www.youtube.com/watch?v=Qcv1IqHWAzg

* pref.b Preferences of boy b

* pref.g Preferences of girl g

If debug Then

Call dbg arg(1)

{{out}}

<pre>

DAN matches FAY</pre>

 

 

 

 

 

else

 

}

 

 

 

 

 

 

}

}

 

 

{{out}}

See Java output.

 

=={{header|Seed7}}==

 

const type: preferences is hash [string] array string;

writeln;

writeln("Marriages are " <& [] ("unstable", "stable") [succ(ord(check(engagedTo, guyPrefers, girlPrefers)))]);

 

Output:

 

=={{header|Sidef}}==

abe => < abi eve cath ivy jan dee fay bea hope gay >,

bob => < cath hope abi dee eve fay bea jan ivy gay >,

 

perturb_em();

{{out}}

<pre>

 

The data set package:

is

 

 

end Preferences;

The package for creating the engagements and checking stability. This package can be analysed by the SPARK tools and proved to be free of any run-time error.

--# inherit Preferences;

package Propose

 

end Propose;

use type Preferences.Extended_Rank;

use type Preferences.Girl;

 

end Propose;

The test program tests all pairwise exchanges. This is Ada, it is not SPARK.

 

(Text IO is quite tedious in SPARK - it's not what the language was designed for.)

-- Test program.

--