2010-09-29, 01:35 AM
You don't need an array of size n!.
Define a table, like[x][y], as the likeability of woman x with man y, for x and y in [1..n]. Then make a list L = [1..n] representing the men, and recurse through all possible permutations of L. Each permutation P represents a pairing, where woman k is paired with man P[k].
One possible permutation algorithm is described here: http://www.bearcave.com/random_hacks/permute.html
Personally I think the second one is the simplest to understand. Essentially you call the recursive function with a sequence and a starting number "start". The subsequence consisting of the first "start" items constitute the part of the permutation that is already built. Then it loops through all the remaining permutations by calling itself once for each remaining item as the next item in the subsequence.
Instead of printing the output at the last level of recursion, call a function that loops through the permutation and sums the likeability of each pairing. Since woman k is paired with man P[k], this is the sum of like[k][P[k]] for all k in [1..n].
Define a table, like[x][y], as the likeability of woman x with man y, for x and y in [1..n]. Then make a list L = [1..n] representing the men, and recurse through all possible permutations of L. Each permutation P represents a pairing, where woman k is paired with man P[k].
One possible permutation algorithm is described here: http://www.bearcave.com/random_hacks/permute.html
Personally I think the second one is the simplest to understand. Essentially you call the recursive function with a sequence and a starting number "start". The subsequence consisting of the first "start" items constitute the part of the permutation that is already built. Then it loops through all the remaining permutations by calling itself once for each remaining item as the next item in the subsequence.
Instead of printing the output at the last level of recursion, call a function that loops through the permutation and sums the likeability of each pairing. Since woman k is paired with man P[k], this is the sum of like[k][P[k]] for all k in [1..n].