weighted matching 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
