To bring together the concepts presented in this chapter, a case study on stable marriages will now be analyzed. The aims of this study are to
1. Show how a program is designed using the top-down approach
2. Show that storing the "right" information in the "right" way has an important effect on the design of a program, on the execution time, and on the memory requirements
3. Demonstrate the concept of data abstraction by treating data and basic operations on it as a unit
4. Illustrate the treatment of arrays and array indices
Consider Table 2.1. It represents the preferences that each of five men and five women has expressed for the five members of the opposite sex. For example, the first man has ranked the women in the order 2, 4, 3, 1, 5.
Now suppose the group has paired off and married, as in Table 2.2. Mi is said to be stable with respect to Wj if there is no other woman preferred by Mi to Wj who, in turn, prefers Mi to her mate. Similarly, Wj is stable with respect to Mi if there is no other man Wj prefers to Mi who prefers Wj to his mate. Any pair (say, Mi-Wj) is stable if each is stable with respect to the other. An entire pairing is stable if all its pairs are stable; an entire pairing is not stable if there exist a man and a woman who are not mates but who prefer each other to their mates.
Consider the pair M3-W1 of Table 2.2. Since M3 prefers W1 to all others, he is stable with respect to W1. W1 prefers M1 and M5 to M3. M1 is married to W4 and does not prefer W1 to W4. M5 is married to W5 and does not prefer W1 to W5. Thus W1 is also stable with respect to M3. Hence the pair is stable. The entire pairing is not stable. For instance, M2 and W3 are paired, but W3 prefers M4 to her mate, and M4 prefers W3 to his mate, so M2-W3 is not a stable pair. Determining whether or not an entire pairing such as that of Table 2.2 is stable may appear frivolous as stated, but there are other applications. Instead of using the terms men, women, and marriage preferences, we might consider tasks, employees, the employees' preferences for performing the tasks, and the ranking of employees by how well they perform the tasks. Or students might provide their preferences for majors while each department gives its preferences for each student.
2.5.1 The ProblemStability of an Entire Pairing
2.5.4 Review of the Program's Development
2.5.5 Generating Stable Pairings
Table 2.1 Preferences
Men's Women's
------------------------------------
M1 2 4 3 1 5 W1 1 5 3 4 2
M2 3 5 2 1 4 W2 4 5 3 2 1
M3 1 5 4 2 3 W3 3 1 4 2 5
M4 3 1 2 5 4 W4 4 2 5 1 3
M5 2 5 1 4 3 W5 1 3 2 4 5
Table 2.2 Pairings
Men Women
----------
1 4
2 3
3 1
4 2
5 5