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}}==

:: Batch File Implementation

 

set "!%~1.tmp!_=%~2"

set "!%~2.tmp!_=%~1"

{{Out}}

<pre>HISTORY:

=={{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:

=={{header|C sharp|C#}}==

(This is a straight-up translation of the Objective-C version.)

using System.Collections.Generic;

 

}

}

 

{{out}}

 

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

#include <iostream>

#include <map>

 

check_stability(engaged, men_pref, women_pref);

{{out}}

<pre>

 

=={{header|Ceylon}}==

 

shared String name;

}

print("``if(!stabilityFlag) then "Not " else ""``Stable!");

{{out}}

<pre>------ the matchmaking process ------

 

=={{header|CoffeeScript}}==

constructor: (@name, @preferences) ->

@mate = null

perturb guys

report_on_mates guys

{{out}}

<pre>

 

=={{header|ColdFusion}}==

PERSON.CFC

 

}

}

INDEX.CFM

 

}

</cfscript>

{{out}}

<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)

The state here consists of the list of free guys and associative preferences lists for guys and girls correspondingly. In order to simplify the access to elements of the state we use lenses.

 

import Lens.Micro

import Lens.Micro.TH

, _girls :: [Preferences a]}

 

 

Lenses allow us to get access to each person in the state, and even to the associated preference list:

 

where get = head . dropWhile ((/= n).fst)

set assoc (_,v) = let (prev, _:post) = break ((== n).fst) assoc

 

fianceesOf n = guys.name n._2

 

Note that in following we use lens operators:

With these tools and notes we are ready to implement the Gale/Shapley algorithm and the stability test as they are given in a textbook:

 

stableMatching = getPairs . until (null._freeGuys) step

where

, elemIndex w2 fm < elemIndex w1 fm

, let fw = s^.fiancesOf w2

 

This solution works not only for strings, but for any equable data.

Here are the given preferences:

 

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

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

("hope", ["gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"]),

("ivy", ["ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"]),

The initial state:

 

 

And the solution:

 

=={{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}}

Jon & Fred swap partners

Stable = No</pre>

 

=={{header|Julia}}==

# This is not optimized, but tries to follow the pseudocode given the Wikipedia entry below.

# Reference: https://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithm

tableprint("Original Data With Bob and Abe Switched", answer[1], stabl)

 

{{out}}

<pre>

=={{header|Kotlin}}==

 

data class Person(val name: String) {

val preferences = mutableListOf<Person>()

println("#### match is stable: ${isStableMatch(males, females)}")

}

{{out}}

<pre>

{{trans|C#}}

 

Person.__index = Person

 

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

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

 

{{out}}

Stable: false

</pre>

 

=={{header|Nim}}==

 

const

echo "Current pair analysis:"

discard checkPairStability(contPairs, recPairs)

{{out}}

<pre>abe 💑 ivy

{{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>

=={{header|Phix}}==

{{trans|AutoHotkey}}

{{Out}}

<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:

 

=={{header|Racket}}==

#lang racket

 

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

(check-stability)

 

Sample run:

{{Works with|rakudo|2016.10}}

{{trans|Perl}}

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

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

engage('fred', 'abi');

engage('jon', 'bea');

{{out}}

<pre>Matchmaking:

=={{header|REXX}}==

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

* pref.b Preferences of boy b

* pref.g Preferences of girl g

s=left(s,p-1)||new||substr(s,p+length(old))

End

{{out}}

<pre>

 

=={{header|Ruby}}==

def initialize(name)

@name = name

 

@men.each_value.collect {|man| puts "#{man} + #{man.fiance}"}

{{out}}

<pre>abe + ivy

=={{header|Scala}}==

{{trans|Java}}

private def checkMarriages(): Unit =

if (check)

swap()

checkMarriages()

{{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}}==

{{trans|Raku}}

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.

--

 

end MatchMaker;

The begining of the output from the test. All pairwise exchanges create unstable pairings.

<pre>ABI marries JON

=={{header|Swift}}==

{{trans|JavaScript}}

let name:String

var candidateIndex = 0

}

 

{{out}}

<pre>

=={{header|Tcl}}==

{{trans|Python}}

 

# Functions as aliases to standard commands

}

puts ""

{{out}}

<pre>

{{works with|Bourne Again Shell|4.0}}

{{trans|AutoHotkey}}

main() {

# Our ten males:

}

 

{{Out}}

<pre>abi accepted abe

 

=={{header|Ursala}}==

 

{

'stable': match/men women,

'perturbed': ~&lSrSxPp match/men women,

The matches are perturbed by reversing the order of the women.

{{out}}

 

'''The string approach'''<br/>

c00 = "_abe abi eve cath ivy jan dee fay bea hope gay " & _

"_bob cath hope abi dee eve fay bea jan ivy gay " & _

MsgBox Replace(Join(Filter(Split(c00), "-"), vbLf), "_", "")

 

'''The Dictionary approach'''

 

Set d_00 = CreateObject("scripting.dictionary")

Set d_01 = CreateObject("scripting.dictionary")

MsgBox Join(d_00.items, vbLf)

 

{{out}}

{{libheader|Wren-dynamic}}

Although this is a faithful translation, the results are not identical to those of Go as map iteration order in both languages is undefined.

 

var mPref = {

if (!validateStable.call(ps, mPref, wPref)) return

// if those happened to be stable as well, perturb more

 

{{out}}

Assume that the input is in XML form as listed [[Stable marriage problem/XSLT input|here]]. The following XSLT 2.0 style-sheet...

 

xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

xmlns:fn="http://www.w3.org/2005/xpath-functions"

</xsl:function>

 

...when applied to the said input document will yield...

 

<m:stable-marriage-problem-result xmlns:m="http://rosettacode.org/wiki/Stable_marriage_problem">

<m:solution is-stable="true">

<m:message>The perturbed configuration is unstable.</m:message>

</m:stable-marriage-problem-result>

 

=={{header|zkl}}==

{{trans|PicoLisp}}

Boys=Dictionary(

"abe", "abi eve cath ivy jan dee fay bea hope gay".split(),

Couples.filter1("holds","fred")[1]="abi";

Couples.filter1("holds","jon") [1]="bea";

{{out}}

<pre>