Good book, I happen to have it.
Example what I learned from it, putting theory into practice:
program GaleShapley2;
type
range = 1..4;
TPreferences = array[range, range] of Integer;
TMatches = array[range] of Integer;
TProposed = array[range, range] of Boolean;
var
menPreferences:TPreferences = (
(1, 2, 3, 4),
(2, 3, 1, 4),
(3, 1, 2, 4),
(4, 2, 1, 3)
);
womenPreferences:TPreferences = (
(2, 1, 3, 4),
(1, 2, 3, 4),
(3, 2, 1, 4),
(4, 3, 2, 1)
);
womenMatches: TMatches;
proposals: TProposed;
freeMen: array[range] of Boolean;
function Rank(woman, man: Integer): Integer;
var i: Integer;
begin
for i in range do
if womenPreferences[woman, i] = man then
begin
Rank := i;
exit;
end;
end;
procedure StableMarriage;
var
m, w, i, currentPartner, rankNew, rankCurrent: Integer;
done: Boolean;
begin
for i in range do
begin
freeMen[i] := True;
womenMatches[i] := 0;
end;
while True do
begin
done := True;
for m in range do
begin
if freeMen[m] then
begin
for i in range do
begin
w := menPreferences[m, i];
if not proposals[m, w] then
begin
proposals[m, w] := True;
if womenMatches[w] = 0 then
begin
womenMatches[w] := m;
freeMen[m] := False;
end
else
begin
currentPartner := womenMatches[w];
rankNew := Rank(w, m);
rankCurrent := Rank(w, currentPartner);
if rankNew < rankCurrent then
begin
womenMatches[w] := m;
freeMen[m] := False;
freeMen[currentPartner] := True;
end;
end;
break;
end;
end;
done := False;
end;
end;
if done then break;
end;
end;
var
w:integer;
begin
StableMarriage;
for w in range do
writeln('Woman ', w, ' is matched with Man ', womenMatches[w]);
end.
I have improved my original, which you made me do
You should pay for my coffee....
It really is a good book, but I suggest it is not for beginners:
You need to be versed in theory to make examples like the above.
(This example was again improved and modified aided by AI, in this case CoPilot, to review correctness quickly and verified by deepseek)
p.s. I am trying to always state if my code is helped by AI. Everybody should do so.
I wrote the original code but adapted it slightly because of good pointers.
Two models agree it is good code.
Recent
