Stable marriage problem: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 727: | Line 727: | ||
Fred (w/ Cath) and Abi (w/ Jon) prefer each other over current pairing. |
Fred (w/ Cath) and Abi (w/ Jon) prefer each other over current pairing. |
||
Marriages not stable</pre> |
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++}}== |
=={{header|C++}}== |
||
Line 907: | Line 1,051: | ||
eve prefers jon over hal and jon prefers eve over bea |
eve prefers jon over hal and jon prefers eve over bea |
||
</pre> |
</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|Ceylon}}== |
=={{header|Ceylon}}== |
||
Line 1,718: | Line 1,718: | ||
Nope, now everything is broken. Sharing spouses doesn't work, kids. |
Nope, now everything is broken. Sharing spouses doesn't work, kids. |
||
</pre> |
</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
From the Python and Java versions: |
From the Python and Java versions: |
||
Line 4,429: | Line 4,430: | ||
bea prefers fred to jon and fred prefers bea to abi |
bea prefers fred to jon and fred prefers bea to abi |
||
</pre> |
</pre> |
||
=={{header|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|Phix}}== |
=={{header|Phix}}== |
||
Line 5,620: | Line 5,507: | ||
fay and jon like each other better than their present partners: dan and bea, respectively |
fay and jon like each other better than their present partners: dan and bea, respectively |
||
Engagement stability check FAILED</pre> |
Engagement stability check FAILED</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|Racket}}== |
=={{header|Racket}}== |
||
Line 5,932: | Line 5,614: | ||
Unstable: bob and abi prefer each other over partners. |
Unstable: bob and abi prefer each other over partners. |
||
</pre> |
</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}}== |
=={{header|REXX}}== |
||
Line 6,163: | Line 5,961: | ||
COL matches DEE |
COL matches DEE |
||
DAN matches FAY</pre> |
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}}== |
=={{header|Scala}}== |
||
Line 6,884: | Line 6,887: | ||
Pairs are Unstable: JON and ABI prefer each other. |
Pairs are Unstable: JON and ABI prefer each other. |
||
</pre> |
</pre> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
{{trans|JavaScript}} |
{{trans|JavaScript}} |