Forget about arranged, random....marriages, just apply the following cool algorithm:
We'll consider a city with n men and n women. Each woman express her marrying preferences by ranking the men from 1 to n. Similarly, each man ranks women in order of preference from 1 to n.
A set of marriage pairings is unstable if there is at least one pair (men_i, woman_k) and (man_l, woman_h) such that woman_h prefers man_i over man_l and similarly, man_i prefers woman_h over woman_k
A set of marriage parings is stable if there are no unstable pairs.
The following algorithm finds a stable marriage paring for all the men and women in city:
1. For each man and woman sort their list of choices by preference.
2. all men and women are initially free
3. men propose to their number one choice.
4. women wait until all free men have proposed and tentatively say ?yes? to their best suitor
5. while there are free men
- men propose to their highest choice they haven?t proposed yet
- if the woman is free she becomes engaged to the new suitor
- else she breaks up her previous engagement (that man is now free) and she tentatively becomes engaged to the new suitor
6. when done, all engaged pairs get married
If you do use this algorithm, make sure you are the one doing the "proposes" since you'll end up with better choices than the "engagers".
good luck
We'll consider a city with n men and n women. Each woman express her marrying preferences by ranking the men from 1 to n. Similarly, each man ranks women in order of preference from 1 to n.
A set of marriage pairings is unstable if there is at least one pair (men_i, woman_k) and (man_l, woman_h) such that woman_h prefers man_i over man_l and similarly, man_i prefers woman_h over woman_k
A set of marriage parings is stable if there are no unstable pairs.
The following algorithm finds a stable marriage paring for all the men and women in city:
1. For each man and woman sort their list of choices by preference.
2. all men and women are initially free
3. men propose to their number one choice.
4. women wait until all free men have proposed and tentatively say ?yes? to their best suitor
5. while there are free men
- men propose to their highest choice they haven?t proposed yet
- if the woman is free she becomes engaged to the new suitor
- else she breaks up her previous engagement (that man is now free) and she tentatively becomes engaged to the new suitor
6. when done, all engaged pairs get married
If you do use this algorithm, make sure you are the one doing the "proposes" since you'll end up with better choices than the "engagers".
good luck