How can I implement the Gale-Shapley stable marriage algorithm in Perl?
- by srk
Problem :
We have equal number of men and women.each men has a preference score toward each woman. So do the woman for each man.
each of the men and women have certain interests. Based on the interest we calculate the preference scores.
So initially we have an input in a file having x columns. First column is the person(men/woman) id. id are nothing but 0.. n numbers.(first half are men and next half woman) the remaining x-1 columns will have the interests. these are integers too.
now using this n by x-1 matrix... we have come up with a n by n/2 matrix. the new matrix has all men and woman as their rows and scores for opposite sex in columns.
We have to sort the scores in descending order, also we need to know the id of person related to the scores after sorting.
So here i wanted to use hash table.
once we get the scores we need to make up pairs.. for which we need to follow some rules.
My trouble is with the second matrix of n by n/2 that needs to give information of which man/woman has how much preference on a woman/man. I need these scores sorted so that i know who is the first preferred woman/man, 2nd preferred and so on for a man/woman.
I hope to get good suggestions on the data structures i use.. I prefer php or perl.
Thank you in advance
Hey guys this is not an home work. This a little modified version of stable marriage algorithm. I have working solution. I am only working on optimizing my code.
more info:
It is very similar to stable marriage problem but here we need to calculate the scores based on the interests they share. So i have implemented it as the way you see in the wiki page http://en.wikipedia.org/wiki/Stable_marriage_problem. my problem is not solving the problem. i solved it and can run it. I am just trying to have a better solution. so i am asking suggestions on the type of data structure to use. Conceptually I tried using an array of hashes. where the array index give the person id and the hash in it gives the id's <= score's in sorted manner. I initially start with an array of hashes. now i sort the hashes on values, but i could not store the sorted hashes back in an array.So just stored the keys after sorting and used these to get the values from my initial unsorted hashes.
Can we store the hashes after sorting ?
Can you suggest a better structure ?
