+/EE360C

algorithms

git clone https://git.julia.blue/+/EE360C

Joseph RyanAdd labs 1 and 215a3727

master
990 B31 linesraw
1public abstract class AbstractProgram1 {
2    public abstract boolean isStableMatching(Matching marriage);
3
4    /**
5     * Brute force solution to the Stable Marriage problem. Relies on the
6     * function isStableMatching(Matching) to determine whether a candidate
7     * Matching is stable.
8     *
9     * @return A stable Matching.
10     */
11    public Matching stableMarriageBruteForce(Matching marriage) {
12        int n = marriage.getStudentCount();
13        int slots = marriage.totalInternshipSlots();
14
15        Permutation p = new Permutation(n, slots);
16        Matching matching;
17        while ((matching = p.getNextMatching(marriage)) != null) {
18            if (isStableMatching(matching)) {
19                return matching;
20            }
21        }
22
23        return new Matching(marriage);
24    }
25
26    public abstract Matching
27    stableMarriageBruteForce_studentoptimal(Matching marriage);
28
29    public abstract Matching
30    stableMarriageGaleShapley_studentoptimal(Matching marriage);
31}