Stable marriage problem: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 727:
Fred (w/ Cath) and Abi (w/ Jon) prefer each other over current pairing.
Marriages not stable</pre>
=={{header|C sharp|C#}}==
(This is a straight-up translation of the Objective-C version.)
<lang csharp>using System;
using System.Collections.Generic;
namespace StableMarriage
{
class Person
{
private int _candidateIndex;
public string Name { get; set; }
public List<Person> Prefs { get; set; }
public Person Fiance { get; set; }
public Person(string name) {
Name = name;
Prefs = null;
Fiance = null;
_candidateIndex = 0;
}
public bool Prefers(Person p) {
return Prefs.FindIndex(o => o == p) < Prefs.FindIndex(o => o == Fiance);
}
public Person NextCandidateNotYetProposedTo() {
if (_candidateIndex >= Prefs.Count) return null;
return Prefs[_candidateIndex++];
}
public void EngageTo(Person p) {
if (p.Fiance != null) p.Fiance.Fiance = null;
p.Fiance = this;
if (Fiance != null) Fiance.Fiance = null;
Fiance = p;
}
}
static class MainClass
{
static public bool IsStable(List<Person> men) {
List<Person> women = men[0].Prefs;
foreach (Person guy in men) {
foreach (Person gal in women) {
if (guy.Prefers(gal) && gal.Prefers(guy))
return false;
}
}
return true;
}
static void DoMarriage() {
Person abe = new Person("abe");
Person bob = new Person("bob");
Person col = new Person("col");
Person dan = new Person("dan");
Person ed = new Person("ed");
Person fred = new Person("fred");
Person gav = new Person("gav");
Person hal = new Person("hal");
Person ian = new Person("ian");
Person jon = new Person("jon");
Person abi = new Person("abi");
Person bea = new Person("bea");
Person cath = new Person("cath");
Person dee = new Person("dee");
Person eve = new Person("eve");
Person fay = new Person("fay");
Person gay = new Person("gay");
Person hope = new Person("hope");
Person ivy = new Person("ivy");
Person jan = new Person("jan");
abe.Prefs = new List<Person>() {abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay};
bob.Prefs = new List<Person>() {cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay};
col.Prefs = new List<Person>() {hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan};
dan.Prefs = new List<Person>() {ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi};
ed.Prefs = new List<Person>() {jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay};
fred.Prefs = new List<Person>() {bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay};
gav.Prefs = new List<Person>() {gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay};
hal.Prefs = new List<Person>() {abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee};
ian.Prefs = new List<Person>() {hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve};
jon.Prefs = new List<Person>() {abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope};
abi.Prefs = new List<Person>() {bob, fred, jon, gav, ian, abe, dan, ed, col, hal};
bea.Prefs = new List<Person>() {bob, abe, col, fred, gav, dan, ian, ed, jon, hal};
cath.Prefs = new List<Person>() {fred, bob, ed, gav, hal, col, ian, abe, dan, jon};
dee.Prefs = new List<Person>() {fred, jon, col, abe, ian, hal, gav, dan, bob, ed};
eve.Prefs = new List<Person>() {jon, hal, fred, dan, abe, gav, col, ed, ian, bob};
fay.Prefs = new List<Person>() {bob, abe, ed, ian, jon, dan, fred, gav, col, hal};
gay.Prefs = new List<Person>() {jon, gav, hal, fred, bob, abe, col, ed, dan, ian};
hope.Prefs = new List<Person>() {gav, jon, bob, abe, ian, dan, hal, ed, col, fred};
ivy.Prefs = new List<Person>() {ian, col, hal, gav, fred, bob, abe, ed, jon, dan};
jan.Prefs = new List<Person>() {ed, hal, gav, abe, bob, jon, col, ian, fred, dan};
List<Person> men = new List<Person>(abi.Prefs);
int freeMenCount = men.Count;
while (freeMenCount > 0) {
foreach (Person guy in men) {
if (guy.Fiance == null) {
Person gal = guy.NextCandidateNotYetProposedTo();
if (gal.Fiance == null) {
guy.EngageTo(gal);
freeMenCount--;
} else if (gal.Prefers(guy)) {
guy.EngageTo(gal);
}
}
}
}
foreach (Person guy in men) {
Console.WriteLine("{0} is engaged to {1}", guy.Name, guy.Fiance.Name);
}
Console.WriteLine("Stable = {0}", IsStable(men));
Console.WriteLine("\nSwitching fred & jon's partners");
Person jonsFiance = jon.Fiance;
Person fredsFiance = fred.Fiance;
fred.EngageTo(jonsFiance);
jon.EngageTo(fredsFiance);
Console.WriteLine("Stable = {0}", IsStable(men));
}
public static void Main(string[] args)
{
DoMarriage();
}
}
}</lang>
{{out}}
<pre>bob is engaged to cath
fred is engaged to bea
jon is engaged to abi
gav is engaged to gay
ian is engaged to hope
abe is engaged to ivy
dan is engaged to fay
ed is engaged to jan
col is engaged to dee
hal is engaged to eve
Stable = True
Switching fred & jon's partners
Stable = False</pre>
=={{header|C++}}==
Line 907 ⟶ 1,051:
eve prefers jon over hal and jon prefers eve over bea
</pre>
=={{header|Ceylon}}==
Line 1,718:
Nope, now everything is broken. Sharing spouses doesn't work, kids.
</pre>
=={{header|D}}==
From the Python and Java versions:
Line 4,429 ⟶ 4,430:
bea prefers fred to jon and fred prefers bea to abi
</pre>
=={{header|Phix}}==
Line 5,620 ⟶ 5,507:
fay and jon like each other better than their present partners: dan and bea, respectively
Engagement stability check FAILED</pre>
=={{header|Racket}}==
Line 5,932 ⟶ 5,614:
Unstable: bob and abi prefer each other over partners.
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2016.10}}
{{trans|Perl}}
<lang perl6>my %he-likes =
abe => < abi eve cath ivy jan dee fay bea hope gay >,
bob => < cath hope abi dee eve fay bea jan ivy gay >,
col => < hope eve abi dee bea fay ivy gay cath jan >,
dan => < ivy fay dee gay hope eve jan bea cath abi >,
ed => < jan dee bea cath fay eve abi ivy hope gay >,
fred => < bea abi dee gay eve ivy cath jan hope fay >,
gav => < gay eve ivy bea cath abi dee hope jan fay >,
hal => < abi eve hope fay ivy cath jan bea gay dee >,
ian => < hope cath dee gay bea abi fay ivy jan eve >,
jon => < abi fay jan gay eve bea dee cath ivy hope >,
;
my %she-likes =
abi => < bob fred jon gav ian abe dan ed col hal >,
bea => < bob abe col fred gav dan ian ed jon hal >,
cath => < fred bob ed gav hal col ian abe dan jon >,
dee => < fred jon col abe ian hal gav dan bob ed >,
eve => < jon hal fred dan abe gav col ed ian bob >,
fay => < bob abe ed ian jon dan fred gav col hal >,
gay => < jon gav hal fred bob abe col ed dan ian >,
hope => < gav jon bob abe ian dan hal ed col fred >,
ivy => < ian col hal gav fred bob abe ed jon dan >,
jan => < ed hal gav abe bob jon col ian fred dan >,
;
my %fiancé;
my %fiancée;
my %proposed;
sub she-prefers ($her, $hottie) { .index($hottie) < .index(%fiancé{$her}) given ~%she-likes{$her} }
sub he-prefers ($him, $hottie) { .index($hottie) < .index(%fiancée{$him}) given ~%he-likes{$him} }
match'em;
check-stability;
perturb'em;
check-stability;
sub match'em { #'
say 'Matchmaking:';
while unmatched-guy() -> $guy {
my $gal = preferred-choice($guy);
%proposed{"$guy $gal"} = '❤';
if not %fiancé{$gal} {
engage($guy, $gal);
say "\t$gal and $guy";
}
elsif she-prefers($gal, $guy) {
my $engaged-guy = %fiancé{$gal};
engage($guy, $gal);
%fiancée{$engaged-guy} = '';
say "\t$gal dumped $engaged-guy for $guy";
}
}
}
sub check-stability {
my @instabilities = gather for flat %he-likes.keys X %she-likes.keys -> $m, $w {
if he-prefers($m, $w) and she-prefers($w, $m) {
take "\t$w prefers $m to %fiancé{$w} and $m prefers $w to %fiancée{$m}";
}
}
say 'Stablility:';
if @instabilities {
.say for @instabilities;
}
else {
say "\t(all marriages stable)";
}
}
sub unmatched-guy { %he-likes.keys.first: { not %fiancée{$_} } }
sub preferred-choice($guy) { %he-likes{$guy}.first: { not %proposed{"$guy $_" } } }
sub engage($guy, $gal) {
%fiancé{$gal} = $guy;
%fiancée{$guy} = $gal;
}
sub perturb'em { #'
say 'Perturb:';
say "\tengage abi with fred and bea with jon";
engage('fred', 'abi');
engage('jon', 'bea');
}</lang>
{{out}}
<pre>Matchmaking:
cath and bob
ivy and dan
abi and jon
hope and ian
jan and ed
eve and abe
eve dumped abe for hal
ivy dumped dan for abe
fay and dan
gay and gav
bea and fred
dee and col
Stablility:
(all marriages stable)
Perturb:
engage abi with fred and bea with jon
Stablility:
fay prefers jon to dan and jon prefers fay to bea
eve prefers jon to hal and jon prefers eve to bea
gay prefers jon to gav and jon prefers gay to bea
bea prefers fred to jon and fred prefers bea to abi</pre>
=={{header|REXX}}==
Line 6,163 ⟶ 5,961:
COL matches DEE
DAN matches FAY</pre>
=={{header|Ruby}}==
<lang ruby>class Person
def initialize(name)
@name = name
@fiance = nil
@preferences = []
@proposals = []
end
attr_reader :name, :proposals
attr_accessor :fiance, :preferences
def to_s
@name
end
def free
@fiance = nil
end
def single?
@fiance == nil
end
def engage(person)
self.fiance = person
person.fiance = self
end
def better_choice?(person)
@preferences.index(person) < @preferences.index(@fiance)
end
def propose_to(person)
puts "#{self} proposes to #{person}" if $DEBUG
@proposals << person
person.respond_to_proposal_from(self)
end
def respond_to_proposal_from(person)
if single?
puts "#{self} accepts proposal from #{person}" if $DEBUG
engage(person)
elsif better_choice?(person)
puts "#{self} dumps #{@fiance} for #{person}" if $DEBUG
@fiance.free
engage(person)
else
puts "#{self} rejects proposal from #{person}" if $DEBUG
end
end
end
########################################################################
# initialize data
prefs = {
'abe' => %w[abi eve cath ivy jan dee fay bea hope gay],
'bob' => %w[cath hope abi dee eve fay bea jan ivy gay],
'col' => %w[hope eve abi dee bea fay ivy gay cath jan],
'dan' => %w[ivy fay dee gay hope eve jan bea cath abi],
'ed' => %w[jan dee bea cath fay eve abi ivy hope gay],
'fred' => %w[bea abi dee gay eve ivy cath jan hope fay],
'gav' => %w[gay eve ivy bea cath abi dee hope jan fay],
'hal' => %w[abi eve hope fay ivy cath jan bea gay dee],
'ian' => %w[hope cath dee gay bea abi fay ivy jan eve],
'jon' => %w[abi fay jan gay eve bea dee cath ivy hope],
'abi' => %w[bob fred jon gav ian abe dan ed col hal],
'bea' => %w[bob abe col fred gav dan ian ed jon hal],
'cath' => %w[fred bob ed gav hal col ian abe dan jon],
'dee' => %w[fred jon col abe ian hal gav dan bob ed],
'eve' => %w[jon hal fred dan abe gav col ed ian bob],
'fay' => %w[bob abe ed ian jon dan fred gav col hal],
'gay' => %w[jon gav hal fred bob abe col ed dan ian],
'hope' => %w[gav jon bob abe ian dan hal ed col fred],
'ivy' => %w[ian col hal gav fred bob abe ed jon dan],
'jan' => %w[ed hal gav abe bob jon col ian fred dan],
}
@men = Hash[
%w[abe bob col dan ed fred gav hal ian jon].collect do |name|
[name, Person.new(name)]
end
]
@women = Hash[
%w[abi bea cath dee eve fay gay hope ivy jan].collect do |name|
[name, Person.new(name)]
end
]
@men.each {|name, man| man.preferences = @women.values_at(*prefs[name])}
@women.each {|name, woman| woman.preferences = @men.values_at(*prefs[name])}
########################################################################
# perform the matching
def match_couples(men, women)
men.each_value {|man| man.free}
women.each_value {|woman| woman.free}
while m = men.values.find {|man| man.single?} do
puts "considering single man #{m}" if $DEBUG
w = m.preferences.find {|woman| not m.proposals.include?(woman)}
m.propose_to(w)
end
end
match_couples @men, @women
@men.each_value.collect {|man| puts "#{man} + #{man.fiance}"}
########################################################################
# check for stability
class Person
def more_preferable_people
( @preferences.partition {|p| better_choice?(p)} ).first
end
end
require 'set'
def stability(men)
unstable = Set.new
men.each_value do |man|
woman = man.fiance
puts "considering #{man} and #{woman}" if $DEBUG
man.more_preferable_people.each do |other_woman|
if other_woman.more_preferable_people.include?(man)
puts "an unstable pairing: #{man} and #{other_woman}" if $DEBUG
unstable << [man, other_woman]
end
end
woman.more_preferable_people.each do |other_man|
if other_man.more_preferable_people.include?(woman)
puts "an unstable pairing: #{woman} and #{other_man}" if $DEBUG
unstable << [other_man, woman]
end
end
end
if unstable.empty?
puts "these couples are stable"
else
puts "uh oh"
unstable.each do |a,b|
puts "#{a} is engaged to #{a.fiance} but would prefer #{b}, and #{b} is engaged to #{b.fiance} but would prefer #{a}"
end
end
end
stability @men
########################################################################
# perturb
puts "\nwhat if abe and bob swap..."
def swap(m1, m2)
w1 = m1.fiance
w2 = m2.fiance
m1.fiance = w2
w1.fiance = m2
m2.fiance = w1
w2.fiance = m1
end
swap *@men.values_at('abe','bob')
@men.each_value.collect {|man| puts "#{man} + #{man.fiance}"}
stability @men</lang>
{{out}}
<pre>abe + ivy
bob + cath
col + dee
dan + fay
ed + jan
fred + bea
gav + gay
hal + eve
ian + hope
jon + abi
these couples are stable
what if abe and bob swap...
abe + cath
bob + ivy
col + dee
dan + fay
ed + jan
fred + bea
gav + gay
hal + eve
ian + hope
jon + abi
uh oh
bob is engaged to ivy but would prefer cath, and cath is engaged to abe but would prefer bob
bob is engaged to ivy but would prefer hope, and hope is engaged to ian but would prefer bob
bob is engaged to ivy but would prefer abi, and abi is engaged to jon but would prefer bob
bob is engaged to ivy but would prefer fay, and fay is engaged to dan but would prefer bob
bob is engaged to ivy but would prefer bea, and bea is engaged to fred but would prefer bob</pre>
Hmm, turns out Bob is a popular guy...
=={{header|Scala}}==
Line 6,884 ⟶ 6,887:
Pairs are Unstable: JON and ABI prefer each other.
</pre>
=={{header|Swift}}==
{{trans|JavaScript}}
| |||