From ca4d88e67d39d3071304508017e6543ab19d160d Mon Sep 17 00:00:00 2001
From: Gregor Kleen <gkleen@yggdrasil.li>
Date: Wed, 31 May 2017 11:40:49 +0200
Subject: Move stable-marriage-problem to submodule
---
.gitmodules | 3 +
ss2017/stable-marriage-problem | 1 +
ss2017/stable_marriage_problem/ausarbeitung.lhs | 127 ------------------------
ss2017/stable_marriage_problem/orga.md | 21 ----
ss2017/stable_marriage_problem/structure.md | 35 -------
5 files changed, 4 insertions(+), 183 deletions(-)
create mode 160000 ss2017/stable-marriage-problem
delete mode 100644 ss2017/stable_marriage_problem/ausarbeitung.lhs
delete mode 100644 ss2017/stable_marriage_problem/orga.md
delete mode 100644 ss2017/stable_marriage_problem/structure.md
diff --git a/.gitmodules b/.gitmodules
index ce4696e..91b1fd1 100644
--- a/.gitmodules
+++ b/.gitmodules
@@ -4,3 +4,6 @@
[submodule "ss2017/ffp"]
path = ss2017/ffp
url = gitlab.cip.ifi.lmu.de:jost/FFP_SoSe17.git
+[submodule "ss2017/stable-marriage-problem"]
+ path = ss2017/stable-marriage-problem
+ url = git@gitlab.cip.ifi.lmu.de:kleen/stable-marriage-problem
diff --git a/ss2017/stable-marriage-problem b/ss2017/stable-marriage-problem
new file mode 160000
index 0000000..7a5f8b6
--- /dev/null
+++ b/ss2017/stable-marriage-problem
@@ -0,0 +1 @@
+Subproject commit 7a5f8b61fc7caf45f038007613db254660554b46
diff --git a/ss2017/stable_marriage_problem/ausarbeitung.lhs b/ss2017/stable_marriage_problem/ausarbeitung.lhs
deleted file mode 100644
index ca03280..0000000
--- a/ss2017/stable_marriage_problem/ausarbeitung.lhs
+++ /dev/null
@@ -1,127 +0,0 @@
-Preliminaries
-=============
-
- - Efficient finite maps
-
-> import Data.Map (Map, (!))
-> import qualified Data.Map as Map
-
- - Efficient finite sets
-
-> import Data.Set (Set)
-> import qualified Data.Set as Set
-
- - Some convenience functions for manipulating lists and endomorphisms
-
-> import Control.Monad (guard, when)
-> import Data.Monoid (Endo(..))
-
- - An arbitrary representation of a person
-
-> type Person = Integer
-
-Utilities
----------
-
-> (&!) :: a -> [a -> a] -> a
-> -- ^ Reverse application of a list of endomorphisms
-> x &! fs = foldMap Endo fs `appEndo` x
->
-> infix 3 ==>
-> -- | Logical implication
-> (==>) :: Bool -> Bool -> Bool
-> False ==> _ = True
-> True ==> True = True
-> True ==> False = False
-
-<!--
-
-> pPrint :: PreferenceTable -> IO ()
-> pPrint = putStr . unlines . map (\(k, prefs) -> show k ++ ": " ++ unwords (map show prefs)) . Map.toList
->
-> stepPhase1 :: PreferenceTable -> IO (Maybe PreferenceTable)
-> stepPhase1 = phase1Iter Set.empty
-> where
-> phase1Iter :: Set Person -> PreferenceTable -> IO (Maybe PreferenceTable)
-> -- ^ Call `phase1'` until no person is free
-> phase1Iter engaged table = do
-> let r = phase1' engaged table
-> case r of
-> Just (engaged', table') -> do
-> when (table' /= table) $ do
-> pPrint table'
-> () <$ getLine
-> if engaged' == Map.keysSet table'
-> then return (Just table')
-> else phase1Iter engaged' table'
-> Nothing -> return Nothing
-
-
--->
-
-Definitions
-===========
-
-\begin{def*}
-A \emph{preference table} is a finite set of persons, each associated with a list of other persons, ordered by preference.
-\end{def*}
-
-> type PreferenceTable = Map Person [Person]
-
-\begin{def*}
-We call a pair ${a, b}$ \emph{embedded} in a preference table if $a$ occurs in $b$s preference list and vice versa.
-\end{def*}
-
-Deleting a pair from a table means removing each from the others preference list:
-
-> delPair :: (Person, Person) -> (PreferenceTable -> PreferenceTable)
-> delPair (p1, p2) = Map.mapWithKey delPair'
-> where
-> delPair' k v = do
-> z <- v
-> guard $ k == p1 ==> z /= p2
-> guard $ k == p2 ==> z /= p1
-> return z
-
-\begin{def*}
-An ordered pair $(a, b)$ is said to be \emph{semiengaged} if $a$ occurs last in $b$s preference table and $b$ occurs first in $a$s.
-
-This means that, while $b$ is $a$s best choice of partner, $a$ has no worse choice in partner than $a$
-\end{def*}
-
-> semiEngaged :: (Person, Person) -> PreferenceTable -> Bool
-> -- ^ `semiEngaged (x, y)`; is `x` last in `y`s preference list?
-> semiEngaged (x, y) table = x == (last $ table ! y)
-
-Phase 1
-=======
-
-> phase1' :: Set Person -> PreferenceTable -> Maybe (Set Person, PreferenceTable)
-> phase1' engaged table
-> | any null (Map.elems table)
-> = Nothing -- If a preference list became empty: fail
-> | Set.null free
-> = Just (engaged, table) -- If nobody is free, we have nobody left to engage
-> | otherwise
-> = let x = Set.findMin free -- Arbitrary choice of free person
-> y = head $ table ! x -- Best choice of engagement for x
-> adjTable = [ delPair (x', y) | x' <- dropWhile (/= x) (table ! y), x' /= x ]
-> -- ^ For all worse (than x) choices x' for y; drop them from y's preference list
-> adjEngaged = [ Set.insert x -- x is now engaged
-> ] ++ [ Set.delete z | z <- Map.keys table, semiEngaged (z, y) table, z /= x ] -- Nobody else is engaged to y
-> in Just (engaged &! adjEngaged, table &! adjTable)
-> where
-> free = Map.keysSet table `Set.difference` engaged
-
-The algorithm is iterated until all participants are engaged
-
-> phase1 :: PreferenceTable -> Maybe PreferenceTable
-> phase1 = phase1Iter Set.empty
-> where
-> phase1Iter :: Set Person -> PreferenceTable -> Maybe PreferenceTable
-> -- ^ Call `phase1'` until no person is free
-> phase1Iter engaged table = do
-> (engaged', table') <- phase1' engaged table
-> if engaged' == Map.keysSet table'
-> then return table'
-> else phase1Iter engaged' table'
diff --git a/ss2017/stable_marriage_problem/orga.md b/ss2017/stable_marriage_problem/orga.md
deleted file mode 100644
index d664ac6..0000000
--- a/ss2017/stable_marriage_problem/orga.md
+++ /dev/null
@@ -1,21 +0,0 @@
-Präsentation/Ausarbeitung: <name/thema>.pdf
-Avg von Note auf erstabgabe und jeweils Verbesserung nach Korrektor
-
-Vertraut machen mit Material bis Vorbesprechung (Inhaltsangabe/Struktur mitbringen)
-
-Vortrag semi-interaktiv
-Eigene Beispiele
-Sauberes Zitieren.
-
-1.) Einführung für lehramt
-2.) implementierung, erweiterung und eigenschaften
-3.) !!!!
-4.) Eigenschaften v. Lösung v. 3.
-5.) Strategische präferenzen
-6.) 2n Personen auf n 2-Person zimmer (stable marriage mit 2n-1 langen präferenzlisten) !!! This one. !!!
-7.) 6.) angewandt auf Schach
-8.) Alle Lösungen zu 1
-9.) Gütertransport in einem Graph !!
-10.) 9 fortsetzung
-11.) Bipartites Matching als Netzwerkfluss
-12.) One-sided matching !
diff --git a/ss2017/stable_marriage_problem/structure.md b/ss2017/stable_marriage_problem/structure.md
deleted file mode 100644
index fa9ac96..0000000
--- a/ss2017/stable_marriage_problem/structure.md
+++ /dev/null
@@ -1,35 +0,0 @@
- - Implement algorithm in haskell, split over single steps
- - During presentation show steps working on examples of the problem (one solves during step 1, one fails during step 1, one that requires multiple rotations to be eliminated), within `ghci`
- - For most important proofs (tbd) show applicable step in haskell code with sketch of proof
-
-
-# Tables
- - Definition: Tables, embedded tables, embedded pairs, embedded matchings
- - Definition: stable tables
- - Matchings embedded in stable tables are stable (4.2.4 ii)
- - Stable tables are determined by all first OR all last entries (4.2.4 iii)
- - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i)
-
-# Phase 1
- - Removal of pairs from tables
- - Engagement
- - Present algorithm and demonstrate
- - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i)
- - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii)
- - Phase 1 results in the largest stable table (4.2.4 iv)
-
-# Rotations
- - Definition: rotation, exposure of rotations in stable tables
- - Directed graphs & tails
- - (Rotations exposed in a stable T are either identical or disjunct (4.2.5))
-
-# Phase 2
- - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6)
- - Elimination of rotations from stable tables
- - ignores non-elements of rotation (4.2.7 iii)
- - results in table consistent with rotation (4.2.7 i, ii)
- - Thus: produce stable subtables (4.2.8)
- - Subtables that don't agree with an exposed rotation have at least that rotation removed entirely (4.2.9)
- - Any subtable can be created by removing a series of exposed rotations (Cor 4.2.2)
- - Removal of rotations preserve matchings (Thm 4.2.1)
- - Present derived algorithm and demonstrate
--
cgit v1.2.3