From ca4d88e67d39d3071304508017e6543ab19d160d Mon Sep 17 00:00:00 2001 From: Gregor Kleen 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 - - - -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: .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