Ada 8 pasang pria (man) dan wanita (woman), maka array yang terbentuk adalah sebagai berikut :
1. man = 8
2. woman = 8
3. rank = 8
4. mP(man, rank) = mP (8, 8)
contoh:
Man\ Rank 1 2 3 4 5 6 7 8
Man 1 select woman 3 6 7 1 8 4 5 2
2 6 3 1 3 5 8 2 7
3 8 4 1 5 6 3 7 2
4 3 8 4 2 5 6 7 1
5 8 3 4 5 6 1 7 2
6 8 7 5 2 4 3 1 6
7 2 4 6 3 1 7 5 8
8 6 1 4 2 7 5 3 8
5. wP(woman, rank) = wP(8, 8)
6. m(man) = m(8)
7. w(woman) = w(8)
8. single(woman) = single(8) = (T, T, T, T, T, T, T, T) merupakan array Boolean
ABSTRAKSI
PROCEDURE try(man,sukses)
r = ranking
FOR r = 1 sampai 8
Pemilihan woman oleh man berdasarkan ranking
IF woman tsb single ?
THEN Pasangkan man dengan woman single dan woman tsb tidak single
IF man<8 THEN CALL try(man+1, sukses_berikut ELSE cetak pasangan Batalkan Pasangan RETURN ANALISA 1. Level = 8 2. Prioritas = 8 3. Ambil tindakan = Pasangkan man dengan woman single dan single = false for (int i = 0; i < m.length; i++) { System.out.println(i + " + " + m[i]); } 4. if tindakan dapat dilakukan = Apakah Wanita tsb single ? int[] single = new int[n]; final int TRUE = -1; for (int i = 0; i < single.length; i++) single[i] = TRUE; for (int i = 0; i < single.length; i++) PriaFree.add(i); int[] next = new int[n]; while (!PriaFree.isEmpty()) { int m = PriaFree.remove(); int w = mP[m][next[m]]; next[m]++; System.out.println("m=" + m + " w=" + w); if (single[w] == TRUE) { single[w] = m; 5. batalkan tindakan = Batalkan Pernikahan(Pilih wanita/pria lain) int m1 = single[w]; if (prefers(w, m, m1)) { single[w] = m; PriaFree.add(m1); } else { PriaFree.add(m); } private boolean prefers(int w, int x, int y) { for (int i = 0; i < 8; i++) { int pref = wP[w][i]; if (pref == x) return true; if (pref == y) return false; } // This should never happen. System.out.println("Error in wP list " + w); return false; } Program import java.util.*; import java.io.*; public class StableMarriage { private int n ; private int[][] mP; private int[][] wP; private static final boolean DEBUGGING = false; private Random rand = new Random(); public static void main(String[] args) { if (args.length != 1) { int n = 8; StableMarriage sm = new StableMarriage(n); if (n <= 10) sm.printPrefTables(); int[] marriage = sm.stable(); if (n <= 10) sm.printMarriage(marriage); return; } } public StableMarriage(int n) { this.n = n; mP = new int[n][]; wP = new int[n][]; for (int i = 0; i < n; i++) { mP[i] = new int[n]; createRandomPrefs(mP[i]); wP[i] = new int[n]; createRandomPrefs(wP[i]); } } private void createRandomPrefs(int[] v) { for (int i = 0; i < v.length; i++) v[i] = i; for (int i = v.length - 1; i > 0; i--) {
int j = rand.nextInt(i+1);
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
public int[] stable() {
int[] single = new int[n];
final int TRUE = -1;
for (int i = 0; i < single.length; i++) single[i] = TRUE; LinkedList
for (int i = 0; i < single.length; i++) PriaFree.add(i); int[] next = new int[n]; while (!PriaFree.isEmpty()) { int m = PriaFree.remove(); int w = mP[m][next[m]]; next[m]++; System.out.println("Pasangan”); System.out.println("m=" + m + " w=" + w); if (single[w] == TRUE) { single[w] = m; } else { int m1 = single[w]; if (prefers(w, m, m1)) { single[w] = m; PriaFree.add(m1); } else { PriaFree.add(m); } } } return single; } private boolean prefers(int w, int x, int y) { for (int i = 0; i < 4; i++) { int pref = wP[w][i]; if (pref == x) return true; if (pref == y) return false; } System.out.println("Error in wP list " + w); return false; } public void printPrefTables() { System.out.println("Man List:"); printMatrix(mP); System.out.println("Woman List:"); printMatrix(wP); } private void printMarriage(int[] m) { System.out.println("Pernikahan: "); for (int i = 0; i < m.length; i++) System.out.println(‘(’ + i + " + " + m[i] + ‘)’); } private void printDebug(String s) { if (DEBUGGING) { System.out.println(s); } } private void printMatrix(int[][] v) { if (v == null) { System.out.println("
return;
}
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++)
System.out.print(v[i][j] + " ");
System.out.println();
}
}
}
HASIL :
Man List
Woman List
Pasangan
Pernikahan :
(0,4)
(1,5)
(2,7)
(3,6)
(4,1)
(5,0)
(6,3)
(7,2)
