+/EE360C
algorithms
git clone https://git.julia.blue/+/EE360C
15a3727
master
1import java .util .ArrayList ; 2import java .util .Arrays ; 3 4public class Permutation { 5private int n ; 6private int k ; 7private boolean allowEmptySpots ; 8 9private long count ; 10private int []studentCounts ; 11private int []pairing ; 12private 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*/ 22public Permutation (int n ,int k ,boolean allowEmptyPositions ) { 23this .n =n ; 24this .k =k ; 25this .allowEmptySpots =allowEmptyPositions ; 26 27this .count =0 ; 28 29this .studentCounts =new int [this .n ]; 30Arrays .fill (this .studentCounts ,0 ); 31this .pairing =new int [this .k ]; 32 33if (allowEmptyPositions ) { 34Arrays .fill (this .pairing , -1 ); 35 }else { 36Arrays .fill (this .pairing ,0 ); 37this .studentCounts [0 ] =this .pairing .length ; 38 } 39 40this .done =false ; 41 } 42 43public 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*/ 52public Matching getNextMatching (Matching data ) { 53int []pairing =getNextPairing (); 54if (pairing ==null ) { 55return null ; 56 } 57 58Matching matching =convertPairingToMatching (data ,pairing ); 59return 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*/ 70private Matching convertPairingToMatching (Matching data ,int []pairing ) { 71int m =data .getInternshipCount (); 72int n =data .getStudentCount (); 73ArrayList <Integer >internship_slots =data .getInternshipSlots (); 74 75int pairing_index =0 ; 76ArrayList <Integer >student_matching =new ArrayList <Integer >(0 ); 77for (int i =0 ;i <n ;i ++) {student_matching .add (-1 ); } 78 79for (int i =0 ;i <m ;i ++) { 80for (int j =0 ;j <internship_slots .get (i );j ++) { 81if (pairing [pairing_index ] != -1 ) { 82student_matching .set (pairing [pairing_index ],i ); 83 } 84 85if (pairing_index ==pairing .length ) { 86break ; 87 } 88 89pairing_index ++; 90 } 91 } 92 93return 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*/ 112private int []getNextPairing () { 113if (done ) { 114return null ; 115 } 116 117count ++; 118 119do {incrementPairing (); }while (!isValidPairing ()); 120 121int []nextPairing =new int [pairing .length ]; 122System .arraycopy (pairing ,0 ,nextPairing ,0 ,pairing .length ); 123return nextPairing ; 124 } 125 126private boolean isValidPairing () { 127for (int x :studentCounts ) { 128if (x >1 ) { 129return false ; 130 } 131 } 132return 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*/ 140private void incrementPairing (int index ) { 141if (index ==0 ) { 142count ++; 143 } 144 145if (index >=pairing .length ) { 146done =true ; 147return ; 148 } 149 150removeStudent (pairing [index ]); 151 152// update students in matching 153pairing [index ]++; 154if (pairing [index ] >=n ) { 155if (allowEmptySpots ) { 156pairing [index ] = -1 ; 157 }else { 158pairing [index ] =0 ; 159 } 160 161incrementPairing (index +1 ); 162 } 163 164addStudent (pairing [index ]); 165 } 166 167private void incrementPairing () {incrementPairing (0 ); } 168 169private void updateStudent (int student ,int update ) { 170if (student == -1 ||student >=n ) { 171return ; 172 } 173 174studentCounts [student ] +=update ; 175 } 176 177private void removeStudent (int student ) {updateStudent (student , -1 ); } 178 179private void addStudent (int student ) {updateStudent (student ,1 ); } 180}