+/EE360C

algorithms

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

Joseph RyanAdd labs 1 and 215a3727

master
5.4 KiB180 linesraw
1import java.util.ArrayList;
2import java.util.Arrays;
3
4public class Permutation {
5    private int n;
6    private int k;
7    private boolean allowEmptySpots;
8
9    private long count;
10    private int[] studentCounts;
11    private int[] pairing;
12    private boolean done;
13
14    /**
15     * Initialize a permutation which will select pairings of students to spots.
16     * There should be at most p pairings. No pairing should be used more than
17     * once. No student should be used more than once.
18     *
19     * @param n Number of students.
20     * @param k Number of spots available.
21     */
22    public Permutation(int n, int k, boolean allowEmptyPositions) {
23        this.n = n;
24        this.k = k;
25        this.allowEmptySpots = allowEmptyPositions;
26
27        this.count = 0;
28
29        this.studentCounts = new int[this.n];
30        Arrays.fill(this.studentCounts, 0);
31        this.pairing = new int[this.k];
32
33        if (allowEmptyPositions) {
34            Arrays.fill(this.pairing, -1);
35        } else {
36            Arrays.fill(this.pairing, 0);
37            this.studentCounts[0] = this.pairing.length;
38        }
39
40        this.done = false;
41    }
42
43    public Permutation(int n, int k) { this(n, k, true); }
44
45    /**
46     * Return the next permutation as a Matching object, representing a solution
47     * to the Stable Matching problem contained in data.
48     *
49     * @param data The Matching object containing the problem to solve.
50     * @return The next candidate solution to the problem.
51     */
52    public Matching getNextMatching(Matching data) {
53        int[] pairing = getNextPairing();
54        if (pairing == null) {
55            return null;
56        }
57
58        Matching matching = convertPairingToMatching(data, pairing);
59        return matching;
60    }
61
62    /**
63     * Return a Matching (StableMarriage candidate) constructed from the int[]
64     * generated by getNextPairing().
65     *
66     * @param data    The Matching object containing the problem to solve.
67     * @param pairing The candidate solution as generated by getNextPairing.
68     * @return The Matching corresponding to the provided pairing.
69     */
70    private Matching convertPairingToMatching(Matching data, int[] pairing) {
71        int m = data.getInternshipCount();
72        int n = data.getStudentCount();
73        ArrayList<Integer> internship_slots = data.getInternshipSlots();
74
75        int pairing_index = 0;
76        ArrayList<Integer> student_matching = new ArrayList<Integer>(0);
77        for (int i = 0; i < n; i++) { student_matching.add(-1); }
78
79        for (int i = 0; i < m; i++) {
80            for (int j = 0; j < internship_slots.get(i); j++) {
81                if (pairing[pairing_index] != -1) {
82                    student_matching.set(pairing[pairing_index], i);
83                }
84
85                if (pairing_index == pairing.length) {
86                    break;
87                }
88
89                pairing_index++;
90            }
91        }
92
93        return new Matching(data, student_matching);
94    }
95
96    /**
97     * Select the next pairing in "ascending order." Each student can be
98     * assigned to at most one spot, and each spot can be assigned to at most
99     * one student, and there are more students than there are spots. Therefore,
100     * the the length of the returned array will be k, and each spot in the
101     * array will contain the index of student which will fill that spot.
102     *
103     * <p>Values for the students range from 0 to n-1, so let the counting
104     * system be a base-n counting system. Each spot in the array must contain
105     * an integer in [0,n-1) and when a position in the array wraps around, the
106     * next highest position is incremented.
107     *
108     * <p>Keep track of the number of instances of a given student's number are
109     * present in the pairing. A pairing is only valid if each student is paired
110     * with a position at most 1 time.
111     */
112    private int[] getNextPairing() {
113        if (done) {
114            return null;
115        }
116
117        count++;
118
119        do { incrementPairing(); } while (!isValidPairing());
120
121        int[] nextPairing = new int[pairing.length];
122        System.arraycopy(pairing, 0, nextPairing, 0, pairing.length);
123        return nextPairing;
124    }
125
126    private boolean isValidPairing() {
127        for (int x : studentCounts) {
128            if (x > 1) {
129                return false;
130            }
131        }
132        return true;
133    }
134
135    /**
136     * Increment one position of the pairing and update arrays appropriately.
137     *
138     * @param index The index of the array to increment.
139     */
140    private void incrementPairing(int index) {
141        if (index == 0) {
142            count++;
143        }
144
145        if (index >= pairing.length) {
146            done = true;
147            return;
148        }
149
150        removeStudent(pairing[index]);
151
152        // update students in matching
153        pairing[index]++;
154        if (pairing[index] >= n) {
155            if (allowEmptySpots) {
156                pairing[index] = -1;
157            } else {
158                pairing[index] = 0;
159            }
160
161            incrementPairing(index + 1);
162        }
163
164        addStudent(pairing[index]);
165    }
166
167    private void incrementPairing() { incrementPairing(0); }
168
169    private void updateStudent(int student, int update) {
170        if (student == -1 || student >= n) {
171            return;
172        }
173
174        studentCounts[student] += update;
175    }
176
177    private void removeStudent(int student) { updateStudent(student, -1); }
178
179    private void addStudent(int student) { updateStudent(student, 1); }
180}