ChatGPT code for GaleShapely Algorithm

Here’s the thing. I wanted to test out the code writing abilities of ChatGPT by assigning it the task of reading a file, and using the Gale Shapely algorithm produce a match for user choice preferences.

As a background:

The Gale-Shapley algorithm is a solution to the stable marriage problem in mathematics and computer science. The problem involves finding a stable pairing between two sets of elements (traditionally referred to as men and women) such that no two elements in one set prefer each other over their current pairing.

The algorithm finds a stable matching between two equal-sized sets by iteratively pairing off the men with their preferred women and resolving any conflicts until all elements are paired. The pairing is considered stable because it cannot be improved for any individual element without making another pairing unstable.

The Gale-Shapley algorithm is considered one of the classic algorithms in the field of matching theory and has applications in a variety of fields, including economics, psychology, and computer science.

Here we illustrate using students and matching them based on their 1st, 2nd and 3rd choice of colleges:

My ChatGPT prompt:
Write python code to read a csv file containing partner choices among members in a club, and using gale shapely algorithm, match them such that all are paired with one of their choice options.

ChatGPT output:

import csv

def gale_shapley(preferences):
n = len(preferences)
engaged = [None] * n
partner_of = [None] * n
next_choice = [0] * n
while None in engaged:
free_man = engaged.index(None)
next_woman = preferences[free_man][next_choice[free_man]]
next_choice[free_man] += 1
if partner_of[next_woman] is None:
engaged[free_man] = next_woman
partner_of[next_woman] = free_man
else:
current_partner = partner_of[next_woman]
if preferences[next_woman].index(current_partner) > preferences[next_woman].index(free_man):
engaged[free_man] = next_woman
engaged[current_partner] = None
partner_of[next_woman] = free_man
return [(i, partner_of.index(i)) for i in range(n) if partner_of[i] is not None]

def read_csv(file_name):
preferences = {}
with open(file_name) as csv_file:
reader = csv.reader(csv_file)
header = next(reader)
for row in reader:
preferences[row[0]] = row[1:]
return [preferences[i] for i in sorted(preferences.keys())]

def write_csv(file_name, pairs):
with open(file_name, ‘w’, newline=’’) as csv_file:
writer = csv.writer(csv_file)
writer.writerow([‘Person’, ‘Partner’])
for (i, j) in pairs:
writer.writerow([i, j])

if __name__ == ‘__main__’:
preferences = read_csv(‘preferences.csv’)
pairs = gale_shapley(preferences)
write_csv(‘pairs.csv’, pairs)

ChatGPT explanation:

Assuming you have a preferences.csv file with the following contents:

Person,Option 1,Option 2,Option 3
A,C,B,D
B,A,D,C
C,B,D,A
D,C,A,B

Running the code will generate a pairs.csv file with the following contents:

Person,Partner
A,B
B,A
C,D
D,C

I havent tried it in Python, but it does look good.