Stable marriage problem: Difference between revisions

Content added Content deleted
Line 199: Line 199:


=={{header|Batch File}}==
=={{header|Batch File}}==
<lang dos>:: Stable Marriage Problem in Rosetta Code
<lang dos>@echo off
:: Batch File Implementation

@echo off
setlocal enabledelayedexpansion
setlocal enabledelayedexpansion


%== Initialization ==%
:: Initialization (Index Starts in 0)
set "male= abe bob col dan ed fred gav hal ian jon" ::First whitespace is necessary
set "male=abe bob col dan ed fred gav hal ian jon"
set "female= abi bea cath dee eve fay gay hope ivy jan" ::same here...
set "femm=abi bea cath dee eve fay gay hope ivy jan"


set "abe[]=abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay"
::Initialization of pseudo-arrays [Male]
set "cnt=0" & for %%. in (abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay) do (set abe[!cnt!]=%%.&set /a cnt+=1)
set "bob[]=cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay"
set "cnt=0" & for %%. in (cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay) do (set bob[!cnt!]=%%.&set /a cnt+=1)
set "col[]=hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan"
set "cnt=0" & for %%. in (hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan) do (set col[!cnt!]=%%.&set /a cnt+=1)
set "dan[]=ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi"
set "cnt=0" & for %%. in (ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi) do (set dan[!cnt!]=%%.&set /a cnt+=1)
set "ed[]=jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay"
set "cnt=0" & for %%. in (jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay) do (set ed[!cnt!]=%%.&set /a cnt+=1)
set "fred[]=bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay"
set "cnt=0" & for %%. in (bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay) do (set fred[!cnt!]=%%.&set /a cnt+=1)
set "gav[]=gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay"
set "cnt=0" & for %%. in (gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay) do (set gav[!cnt!]=%%.&set /a cnt+=1)
set "hal[]=abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee"
set "cnt=0" & for %%. in (abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee) do (set hal[!cnt!]=%%.&set /a cnt+=1)
set "ian[]=hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve"
set "cnt=0" & for %%. in (hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve) do (set ian[!cnt!]=%%.&set /a cnt+=1)
set "jon[]=abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope"
set "cnt=0" & for %%. in (abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope) do (set jon[!cnt!]=%%.&set /a cnt+=1)


set "abi[]=bob, fred, jon, gav, ian, abe, dan, ed, col, hal"
::Initialization of pseudo-arrays [Female]
set "cnt=0" & for %%. in (bob, fred, jon, gav, ian, abe, dan, ed, col, hal) do (set abi[!cnt!]=%%.&set /a cnt+=1)
set "bea[]=bob, abe, col, fred, gav, dan, ian, ed, jon, hal"
set "cnt=0" & for %%. in (bob, abe, col, fred, gav, dan, ian, ed, jon, hal) do (set bea[!cnt!]=%%.&set /a cnt+=1)
set "cath[]=fred, bob, ed, gav, hal, col, ian, abe, dan, jon"
set "cnt=0" & for %%. in (fred, bob, ed, gav, hal, col, ian, abe, dan, jon) do (set cath[!cnt!]=%%.&set /a cnt+=1)
set "dee[]=fred, jon, col, abe, ian, hal, gav, dan, bob, ed"
set "cnt=0" & for %%. in (fred, jon, col, abe, ian, hal, gav, dan, bob, ed) do (set dee[!cnt!]=%%.&set /a cnt+=1)
set "eve[]=jon, hal, fred, dan, abe, gav, col, ed, ian, bob"
set "cnt=0" & for %%. in (jon, hal, fred, dan, abe, gav, col, ed, ian, bob) do (set eve[!cnt!]=%%.&set /a cnt+=1)
set "fay[]=bob, abe, ed, ian, jon, dan, fred, gav, col, hal"
set "cnt=0" & for %%. in (bob, abe, ed, ian, jon, dan, fred, gav, col, hal) do (set fay[!cnt!]=%%.&set /a cnt+=1)
set "gay[]=jon, gav, hal, fred, bob, abe, col, ed, dan, ian"
set "cnt=0" & for %%. in (jon, gav, hal, fred, bob, abe, col, ed, dan, ian) do (set gay[!cnt!]=%%.&set /a cnt+=1)
set "hope[]=gav, jon, bob, abe, ian, dan, hal, ed, col, fred"
set "cnt=0" & for %%. in (gav, jon, bob, abe, ian, dan, hal, ed, col, fred) do (set hope[!cnt!]=%%.&set /a cnt+=1)
set "ivy[]=ian, col, hal, gav, fred, bob, abe, ed, jon, dan"
set "cnt=0" & for %%. in (ian, col, hal, gav, fred, bob, abe, ed, jon, dan) do (set ivy[!cnt!]=%%.&set /a cnt+=1)
set "jan[]=ed, hal, gav, abe, bob, jon, col, ian, fred, dan"
set "cnt=0" & for %%. in (ed, hal, gav, abe, bob, jon, col, ian, fred, dan) do (set jan[!cnt!]=%%.&set /a cnt+=1)
%==/Initialization ==%


rem variable notation:
( %== The main thing ==%
rem <boy>{<index>} = <girl>
echo.HISTORY:
rem <boy>[<girl>] = <index>
for %%M in (%male%) do (
set cnt=0
for %%. in (!%%M[]!) do (
set "%%M{!cnt!}=%%."
set "%%M[%%.]=!cnt!"
set /a cnt+=1
)
)
for %%F in (%femm%) do (
set cnt=0
for %%. in (!%%F[]!) do (
set "%%F[%%.]=!cnt!"
set /a cnt+=1
)
)

:: The Main Thing
echo(HISTORY:
call :stableMatching
call :stableMatching
echo.
echo(
echo.NEWLYWEDS:
echo(NEWLYWEDS:
call :display
call :display
echo.
echo(
call :isStable
call :isStable
echo.
echo(
echo.What if ed and hal swapped?
echo(What if ed and hal swapped?
call :swapper ed hal
call :swapper ed hal
echo.
echo(
echo.NEW-NEWLYWEDS:
echo(NEW-NEWLYWEDS:
call :display
call :display
echo.
echo(
call :isStable
call :isStable
pause>nul
pause>nul
exit /b 0
exit /b 0
) %==/The main thing ==%


%== The algorithm ==%
:: The Algorithm
:stableMatching
:stableMatching
set "free_men=%male%" ::The free-men variable
set "free_men=%male%"
set "free_fem=%femm%"
set "free_women=%female%" ::The free-women variable
for %%M in (%male%) do set "%%M_tried=0"
set nextgirl=0
:thematchloop
set m=&for %%F in (!free_men!) do (if not defined m set "m=%%F")
if "!m!"=="" goto :EOF


:match_loop
for /f "tokens=1-2 delims==" %%A in ('set !m![!nextgirl!]') do set "w=%%B"
if "%free_men%"=="" goto :EOF
set "propo="
for %%W in (!free_women!) do (
if "%%W"=="!w!" (
set propo=TRUE
set "!w!_=!m!" & set "!m!_=!w!"
set free_women=!free_women: %w%=!
set free_men=!free_men: %m%=!
echo. !w! ACCEPTED !m!.
)
)
if defined propo (set "nextgirl=0" & goto thematchloop)


for /f "tokens=1-2 delims==" %%A in ('set !w!_') do set "mbef=%%B"
for /f "tokens=1* delims= " %%m in ("%free_men%") do (
rem get woman not yet proposed to, but if man's tries exceeds the number
set "replace=" & for /f "tokens=1-2 delims==" %%R in ('set !w![') do (
rem of women (poor guy), he starts again to his most preferred woman (#0).
if not defined replace (
for /f %%x in ("!%%m_tried!") do if not defined %%m{%%x} (
if "%%S"=="!m!" (
set "%%m_tried=0" & set "w=!%%m{0}!"
set replace=TRUE
set "!w!_=!m!" & set "!m!_=!w!"
) else set "w=!%%m{%%x}!"
set "m=%%m"
set "free_men=!free_men! !mbef!"
set "free_men=!free_men: %m%=!"
set nextgirl=0
echo. !w! LEFT !mbef!.
echo. !w! ACCEPTED !m!.
)
if "%%S"=="!mbef!" (
set /a nextgirl+=1
set replace=FALSE
)
)
)
goto thematchloop
%==/The Algorithm ==%


for /f %%x in ("free_fem:!w!=") do (
%== Output the Couples ==%
if not "!free_fem!"=="!%%x!" (
rem accept because !w! (the woman) is free
set "!m!_=!w!" & set "!w!_=!m!"
set "free_men=%%n" & set "free_fem=!%%x!"
echo( !w! ACCEPTED !m!.
) else (
rem here, !w! already has a pair; get his name and rank.
for /f %%. in ("!w!") do set "cur_man=!%%._!"
for /f %%. in ("!w![!cur_man!]") do set "rank_cur=!%%.!"
rem also, get the rank of current proposing man.
for /f %%. in ("!w![!m!]") do set "rank_new=!%%.!"

if !rank_new! lss !rank_cur! (
rem here, !w! will leave her pair, and choose !m!.
set "free_men=%%n !cur_man!"
echo( !w! LEFT !cur_man!.
rem pair them up now!
set "!m!_=!w!" & set "!w!_=!m!"
echo( !w! ACCEPTED !m!.
)
)
)
set /a "!m!_tried+=1"
)
goto :match_loop


:: Output the Couples
:display
:display
for %%S in (!male!) do echo. %%S and !%%S_!.
for %%S in (%femm%) do echo. %%S and !%%S_!.
goto :EOF
goto :EOF
%==/Output the Couples ==%


%== Stability Checking ==%
:: Stability Checking
:isStable
:isStable
for %%M in (!female!) do (
for %%f in (%femm%) do (
for %%g in (%male%) do (
set "better="
set "dislike=" & for /f "tokens=1-2 delims==" %%R in ('set %%M[') do (
for /f %%. in ("%%f[!%%f_!]") do set "girl_cur=!%%.!"
set "girl_aboy=!%%f[%%g]!"
if not defined dislike (
if "%%S"=="!%%M_!" (set dislike=T) else (set "better=!better! %%S")
for /f %%. in ("%%g[!%%g_!]") do set "boy_cur=!%%.!"
set "boy_agirl=!%%g[%%f]!"
)

)
if !boy_cur! gtr !boy_agirl! (
for %%X in (!better!) do (
if !girl_cur! gtr !girl_aboy! (
for /f "tokens=1-2 delims==" %%F in ('set %%X_') do set curr_partner_of_boy=%%G
echo(STABILITY = FALSE.
set "main_check="
echo(%%f and %%g would rather be together than their current partners.
for /f "tokens=1-2 delims==" %%B in ('set %%X[') do (
goto :EOF
if not defined main_check (
)
if "%%C"=="%%M" (
)
echo.STABILITY = FALSE.
)
echo %%M and %%X would rather be together than their current partners.
goto :EOF
)
if "%%C"=="!curr_partner_of_boy!" set "main_check=CONTINUE"
)
)
)
)
)
echo.STABILITY = TRUE.
echo(STABILITY = TRUE.
goto :EOF
goto :EOF
%==/Stability Chacking ==%


%== Swapper ==%
:: Swapper
:swapper
:swapper
set %~1.tmp=!%~1_!
set %~1.tmp=!%~1_!
set %~2.tmp=!%~2_!
set %~2.tmp=!%~2_!
set "%~1_=!%~2.tmp!"
set "%~1_=!%~2.tmp!"
set "%~2_=!%~1.tmp!"
set "%~2_=!%~1.tmp!"
set "!%~1.tmp!_=%~2"
set "!%~1.tmp!_=%~2"
set "!%~2.tmp!_=%~1"
set "!%~2.tmp!_=%~1"
goto :EOF
goto :EOF</lang>
%==/Swapper==%</lang>
{{Out}}
{{Out}}
<pre>HISTORY:
<pre>HISTORY:
abi ACCEPTED abe.
abi ACCEPTED abe.
cath ACCEPTED bob.
cath ACCEPTED bob.
hope ACCEPTED col.
hope ACCEPTED col.
ivy ACCEPTED dan.
ivy ACCEPTED dan.
jan ACCEPTED ed.
jan ACCEPTED ed.
bea ACCEPTED fred.
bea ACCEPTED fred.
gay ACCEPTED gav.
gay ACCEPTED gav.
eve ACCEPTED hal.
eve ACCEPTED hal.
hope LEFT col.
hope LEFT col.
hope ACCEPTED ian.
hope ACCEPTED ian.
abi LEFT abe.
abi LEFT abe.
abi ACCEPTED jon.
abi ACCEPTED jon.
dee ACCEPTED col.
dee ACCEPTED col.
ivy LEFT dan.
ivy LEFT dan.
ivy ACCEPTED abe.
ivy ACCEPTED abe.
fay ACCEPTED dan.
fay ACCEPTED dan.


NEWLYWEDS:
NEWLYWEDS:
abe and ivy.
abi and jon.
bob and cath.
bea and fred.
col and dee.
cath and bob.
dan and fay.
dee and col.
ed and jan.
eve and hal.
fred and bea.
fay and dan.
gav and gay.
gay and gav.
hal and eve.
hope and ian.
ian and hope.
ivy and abe.
jon and abi.
jan and ed.


STABILITY = TRUE.
STABILITY = TRUE.
Line 374: Line 385:


NEW-NEWLYWEDS:
NEW-NEWLYWEDS:
abe and ivy.
abi and jon.
bob and cath.
bea and fred.
col and dee.
cath and bob.
dan and fay.
dee and col.
ed and eve.
eve and ed.
fred and bea.
fay and dan.
gav and gay.
gay and gav.
hal and jan.
hope and ian.
ian and hope.
ivy and abe.
jon and abi.
jan and hal.


STABILITY = FALSE.
STABILITY = FALSE.
eve and hal would rather be together than their current partners.</pre>
eve and abe would rather be together than their current partners.</pre>


=={{header|BBC BASIC}}==
=={{header|BBC BASIC}}==
Retrieved from "https://rosettacode.org/wiki/Stable_marriage_problem"