Eşleştirme ve Evlilik (Matching & Marriage) Algoritması

1function galeShapley(
2  menPrefs: Record,
3  womenPrefs: Record
4): Record {
5  const men = Object.keys(menPrefs);
6  const freeMen = [...men];
7  const engagements: Record = {}; // Kadın -> Erkek
8  const proposals: Record = {}; // Erkek -> Teklif indeksi
9
10  for (const m of men) proposals[m] = 0;
11
12  // Yardımcı tercih sırası araması
13  const womenPrefIndex: Record> = {};
14  for (const w of Object.keys(womenPrefs)) {
15    womenPrefIndex[w] = {};
16    womenPrefs[w].forEach((man, rank) => {
17      womenPrefIndex[w][man] = rank;
18    });
19  }
20
21  while (freeMen.length > 0) {
22    const m = freeMen.shift()!;
23    const mList = menPrefs[m];
24    const pIdx = proposals[m];
25
26    if (pIdx < mList.length) {
27      const w = mList[pIdx];
28      proposals[m]++; // Sonraki teklif için
29
30      const currentPartner = engagements[w];
31      if (!currentPartner) {
32        // Kadın bekar
33        engagements[w] = m;
34      } else {
35        // Tercih karşılaştır
36        const rankNew = womenPrefIndex[w][m] ?? Infinity;
37        const rankOld = womenPrefIndex[w][currentPartner] ?? Infinity;
38
39        if (rankNew < rankOld) {
40          engagements[w] = m;
41          freeMen.push(currentPartner); // Eski eş serbest kaldı
42        } else {
43          freeMen.push(m); // Teklif reddedildi
44        }
45      }
46    }
47  }
48
49  return engagements;
50}