To determine whether an entire pairing is stable, the solution must traverse through all the pairs, testing each for stability. The following high-level algorithm does this.
Set stable to true.
For each man, as long as stable is true
set stable to false if the man is not stable with respect to his wife or the wife is not stable with respect to her husband.
The next question is how to determine whether a person is stable. A person is stable if every individual preferred by the person to the person's mate prefers his or her mate to the person. Let stable hold the result of this determination and refine the task:
1. Set individual to whoever is most preferred by person.
2. While (stable and individual ?/FONT> person's mate)
If the individual prefers person to individual's mate, then
set stable to false
else
set individual to whoever is next most preferred by person.
This assumes stable is initially true. Note that the refinement requires
Determining the mate of any person
Choosing the individual most preferred by a person
Determining whether an individual prefers a person to the individual's mate
Finding the individual next most preferred by a person
To follow the dictates of good programming style, the pairings and preference tables should be treated as data abstractions, with their implementation put off until the basic operations on them have become clear. These operations correspond to the four tasks required by the refinement. They will be developed, respectively, as the functions mate, mostpreferred, prefers, and nextpreferred. Before these functions can be written, the implementation of the pairings and the preference data must be decided upon.
Task 1 is to determine a person's mate. This requires the data for the entire pairing, which is given as input to the program and must be read in. However, how should this data be stored? If the mens' pairings are kept in an array mpairs, relating a man to his mate, then the mate of a man can be selected from the array. For the data of Table 2.2, mpairs would be
Thus the mate of man 3 is woman 1. More generally, the mate of man i is found in mpairs[i], the position of mpairs indexed by i. To find the mate of a woman, however, requires a traversal of mpairs. For example, the mate of woman 1 is found by traversing mpairs until an entry with value 1 is located. The array index of this entry, 3, gives the woman's mate. Rather than spending time traversing whenever a woman's mate is needed, storage can be traded for time. To do this, create another array, wpairs, so selection may be used in this case too. Of course, one traversal will still be necessary to generate wpairs, but this is done just once. The wpairs generated from mpairs would be
Task 2 is to find out who is most preferred by a person. Suppose the preferences are implemented as two-dimensional arrays mpref and wpref. If the given preferences are those of Table 2.1, then mpref and wpref would be
Task 2 is then straightforward and can also be done by selection. In each row of these arrays the first entry is the most preferred mate and the last entry is the least preferred. Thus for man 3, mpref[3][1] contains his most preferred mate.
To perform task 3, determining if an individual prefers a person to the individual's mate, the row for that individual in the proper preference array (mpref for a man and wpref for a woman) may be traversed until either the person or the individual's mate is encountered. If the person is encountered first, prefers must return true, and false otherwise.
Finally, task 4, finding the next preferred individual, can be done by using an index to point to the current individual and, after increasing the index by 1, selecting the (person, index) entry from the appropriate preference array.
The task, determining whether a person is stable, can now be further refined.
1. Set individual to mostpreferred (person, pref).
2. Set index to 1.
3. While (stable and individual ?/FONT> person's mate)
a. set individual's mate to mate (individual, pairs),
b. if prefers (individual, person, individual's mate, pref), then
set stable to false
else
i. Increase index by 1,
ii. Set individual to nextpreferred (person, index, pref1).
This assumes that the person's mate is initially set correctly. The implementation for the functions used follows.
To get an idea of the time required for this solution, note that the while loop used in determining stable can require a traversal through a row of pref. This loop may thus be executed (n - 1) times, since rows of pref are of length n (recall that there are n men and n women). During each of these executions, prefers is invoked and can traverse through a row of pref, which is also of length n. The determination of stable can thus take O(n2) time. Since stable may need to be calculated 2n times (twice for each pair), the total time of this solution could be O(n3). We can do better!
The traversal through pref in prefers can be eliminated. It is done simply to determine if the current individual prefers person to individual's mate, and this information can be ferreted out beforehand from pref and summarized in a priority array. This needs to be done only once. Thus the priority array can be produced before the algorithm is invoked, or can be created initially in the main function. One priority array must be created from mpref and another from wpref. The mpriority array can be created from mpref by traversing mpref and processing its (i, j)th entry by setting mpriority [i] [mpref [i] [j]] to j. Similarly, wpriority can be obtained from wpref. Then an individual prefers person to individual's mate if
priority [individual][person] < priority [individual][individual's mate]
For our example, these arrays are as follows:
This version of prefers may be expressed as follows:
When person is male, the parameter priority must be wpriority, and when person is female, priority must be mpriority. The priority arrays result in O(n) time for determining stable, since one traversal is avoided. This reduces the total time of the solution to O(n2). Again, storage has been traded for time. Extracting precisely the relevant information and implementing it properly, just as was done in Example 2.2, is what produced this time saving. Also, this version is clearer and more concise.
mpairs
------
4
3
1
2
5
wpairs
------
3
4
2
1
5
mpref wpref
-----------------------------
2 4 3 1 5 1 5 3 4 2
3 5 2 1 4 4 5 3 2 1
1 5 4 2 3 3 1 4 2 5
3 1 2 5 4 4 2 5 1 3
2 5 1 4 3 1 3 2 4 5
mate(person,pairs)
/* Returns person's mate
as specified by pairs.
*/
int person;
pairings pairs;
{return(pairs[person]);
}
mostpreferred(person,pref)
/* Returns the mate most
preferred by person as
specified by pref.
*/
int person;
preferences pref;
{return(pref[person][1]);
}
prefers(individual,person,individualsmate,pref)
/* Returns true only if individual prefers person
to the individual's mate as specified by pref.
*/
int individual,person,individualsmate;
preferences pref;
{int index,next;
index = 1;
next = pref[individual][1];
while(next != person && next != individualsmate)
{index++;
next = pref[individual][index];
}
if(next == person)
return (TRUE);
else
return(FALSE);
}
nextpreferred(person,index,pref)
/* Returns the mate next most
preferred by person as specified
by pref.
*/
int person,index;
preferences pref;
{return(pref[person][index]);
}
mpriority wpriority
-----------------------------
4 1 3 2 5 1 5 3 4 2
4 3 1 5 2 5 4 3 1 2
1 4 5 3 2 2 4 1 3 5
2 3 1 5 4 4 2 5 1 3
3 1 5 4 2 1 3 2 4 5
prefers(individual,person,individualsmate,priority);
/* Returns true only if individual prefers person
to the individual's mate as specified by priority.
*/
int individual,person,individualsmate;
preferences priority;
{return(priority[individual][person]<
priority[individual][individualsmate]);
}