+/EE360C

algorithms

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

Joseph RyanAdd labs 1 and 215a3727

master
6.2 KiB177 linesraw
1import java.util.ArrayList;
2
3/**
4 * A Matching represents a candidate solution to the Stable Marriage problem. A
5 * Matching may or may not be stable.
6 */
7public class Matching {
8    /**
9     * Number of internships.
10     */
11    private Integer m;
12
13    /**
14     * Number of students.
15     */
16    private Integer n;
17
18    /**
19     * A list containing each internship's preference list.
20     */
21    private ArrayList<ArrayList<Integer>> internship_preference;
22
23    /**
24     * A list containing each student's preference list.
25     */
26    private ArrayList<ArrayList<Integer>> student_preference;
27
28    /**
29     * Number of slots available in each internship.
30     */
31    private ArrayList<Integer> internship_slots;
32    private ArrayList<ArrayList<Integer>> internship_weights;
33    private ArrayList<Double> student_GPA;
34    private ArrayList<Integer> student_months;
35    private ArrayList<Integer> student_projects;
36    /**
37     * Matching information representing the index of internship a student is
38     * matched to, -1 if not matched.
39     *
40     * <p>An empty matching is represented by a null value for this field.
41     */
42    private ArrayList<Integer> student_matching;
43
44    public Matching(Integer m, Integer n,
45                    ArrayList<ArrayList<Integer>> internship_weights,
46                    ArrayList<ArrayList<Integer>> student_preference,
47                    ArrayList<Integer> internship_slots,
48                    ArrayList<Double> student_GPA,
49                    ArrayList<Integer> student_months,
50                    ArrayList<Integer> student_projects) {
51        this.m = m;
52        this.n = n;
53        this.internship_weights = internship_weights;
54        this.student_preference = student_preference;
55        this.internship_slots = internship_slots;
56        this.student_matching = null;
57        this.student_GPA = student_GPA;
58        this.student_months = student_months;
59        this.student_projects = student_projects;
60        internship_preference = Program1.computeInternshipPreferences(
61            getInternshipCount(), getStudentCount(), internship_weights,
62            student_GPA, student_months, student_projects);
63    }
64
65    public Matching(Integer m, Integer n,
66                    ArrayList<ArrayList<Integer>> internship_weights,
67                    ArrayList<ArrayList<Integer>> internship_preference,
68                    ArrayList<ArrayList<Integer>> student_preference,
69                    ArrayList<Integer> internship_slots,
70                    ArrayList<Integer> student_matching,
71                    ArrayList<Double> student_GPA,
72                    ArrayList<Integer> student_months,
73                    ArrayList<Integer> student_projects) {
74        this.m = m;
75        this.n = n;
76        this.internship_preference = internship_preference;
77        this.internship_weights = internship_weights;
78        this.student_preference = student_preference;
79        this.internship_slots = internship_slots;
80        this.student_matching = student_matching;
81        this.student_GPA = student_GPA;
82        this.student_months = student_months;
83        this.student_projects = student_projects;
84    }
85
86    /**
87     * Constructs a solution to the stable marriage problem, given the problem
88     * as a Matching. Take a Matching which represents the problem data with no
89     * solution, and a student_matching which solves the problem given in data.
90     *
91     * @param data              The given problem to solve.
92     * @param student_matching The solution to the problem.
93     */
94    public Matching(Matching data, ArrayList<Integer> student_matching) {
95        this(data.m, data.n, data.getInternshipWeights(),
96             data.internship_preference, data.student_preference,
97             data.internship_slots, student_matching, data.getStudentGPA(),
98             data.getStudentMonths(), data.getStudentProjects());
99    }
100
101    /**
102     * Creates a Matching from data which includes an empty solution.
103     *
104     * @param data The Matching containing the problem to solve.
105     */
106    public Matching(Matching data) {
107        this(data.m, data.n, data.getInternshipWeights(),
108             data.internship_preference, data.student_preference,
109             data.internship_slots, new ArrayList<Integer>(0),
110             data.getStudentGPA(), data.getStudentMonths(),
111             data.getStudentProjects());
112    }
113
114    public void setStudentMatching(ArrayList<Integer> student_matching) {
115        this.student_matching = student_matching;
116    }
117
118    public Integer getInternshipCount() { return m; }
119
120    public Integer getStudentCount() { return n; }
121    public void setInternshipPreference(ArrayList<ArrayList<Integer>> pref) {
122        internship_preference = pref;
123    }
124
125    public ArrayList<ArrayList<Integer>> getInternshipWeights() {
126        return internship_weights;
127    }
128
129    public ArrayList<ArrayList<Integer>> getInternshipPreference() {
130        return internship_preference;
131    }
132
133    public ArrayList<ArrayList<Integer>> getStudentPreference() {
134        return student_preference;
135    }
136
137    public ArrayList<Double> getStudentGPA() { return student_GPA; }
138
139    public ArrayList<Integer> getStudentMonths() { return student_months; }
140
141    public ArrayList<Integer> getStudentProjects() { return student_projects; }
142
143    public ArrayList<Integer> getInternshipSlots() { return internship_slots; }
144
145    public ArrayList<Integer> getStudentMatching() { return student_matching; }
146
147    public int totalInternshipSlots() {
148        int slots = 0;
149        for (int i = 0; i < m; i++) { slots += internship_slots.get(i); }
150        return slots;
151    }
152
153    public String getInputSizeString() {
154        return String.format("m=%d n=%d\n", m, n);
155    }
156
157    public String getSolutionString() {
158        if (student_matching == null) {
159            return "";
160        }
161
162        StringBuilder s = new StringBuilder();
163        for (int i = 0; i < student_matching.size(); i++) {
164            String str = String.format("student %d internship %d", i,
165                                       student_matching.get(i));
166            s.append(str);
167            if (i != student_matching.size() - 1) {
168                s.append("\n");
169            }
170        }
171        return s.toString();
172    }
173
174    public String toString() {
175        return getInputSizeString() + getSolutionString();
176    }
177}