1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @description: Gale-Shapley algorithm
 * @author: Qing Zhang
 * @time: 09
 */
public class GaleShapley {

    /**
     * @Description: GS algorithm
     * note: The number of men must be equal to women.
     * @Param: [
     * paraManPreferences : Men's Descending Preference Array for Women.
     * paraWomanPreferences : Women's Descending Preference Array for Men
     * ]
     * @return: java.util.HashMap<java.lang.Integer, java.lang.Integer>
     */
    public static HashMap<Integer, Integer> gsAlgorithm(int[][] paraManPreferences, int[][] paraWomanPreferences) {

        // initial.
        int numOfMan = paraManPreferences.length; // number of men
        int numOfWoman = paraWomanPreferences.length; // number of women

        if (numOfMan != numOfWoman) {
            System.out.println("The data format is wrong!");
            return null;
        }

        // Record whether women are free
        boolean[] singleWoman = new boolean[numOfWoman];

        // Women’s preference for men, sorted by male number
        int[][] womanPreferencesToMan = new int[numOfWoman][numOfMan];
        for (int i = 0; i < numOfWoman; i++) {
            for (int j = 0; j < numOfMan; j++) {
                womanPreferencesToMan[i][paraWomanPreferences[i][j]] = j;
            }
        }

        // Single man
        Queue<Integer> singleMan = new LinkedList<>();
        // Results after allocation (female, male)
        HashMap<Integer, Integer> lovers = new HashMap<>();
        for (int i = 0; i < numOfMan; i++) {
            singleMan.add(i);
        }

        // Loop... Find the woman for every single man.
        while (!singleMan.isEmpty()) {
            int curMan = singleMan.peek();
            int curWoman;
            for (int i = 0; i < numOfWoman; i++) {
                curWoman = paraManPreferences[curMan][i];
                if (!singleWoman[curWoman]) {
                    lovers.put(curWoman, curMan);
                    singleWoman[curWoman] = true;
                    singleMan.poll();
                    break;
                } else if (womanPreferencesToMan[curWoman][lovers.get(curWoman)]
                        > womanPreferencesToMan[curWoman][curMan]) {
                    singleMan.add(lovers.get(curWoman));
                    lovers.put(curWoman, curMan);
                    singleMan.poll();
                    break;
                }
            }
        }

        return lovers;
    }

    public static void main(String[] args) {
        int[][] man = new int[][]{{0, 1, 2}, {1, 0, 2}, {0, 1, 2}};
        int[][] woman = new int[][]{{1, 0, 2}, {0, 1, 2}, {0, 1, 2}};
        HashMap<Integer, Integer> lovers = GaleShapley.gsAlgorithm(man, woman);

        if (lovers != null) {
            for (Map.Entry<Integer, Integer> entry : lovers.entrySet()) {
                System.out.println(entry.getValue() + "号男性---" + entry.getKey() + "号女性");
            }
        }
    }
}

1
2
3
4
5
6
7
8
C:UsersAdministrator.jdkstemurin-11.0.12-1binjava.exe "-javaagent:E:IntelliJ IDEA 2020.1libidea_rt.jar=56703:E:IntelliJ IDEA 2020.1bin" -Dfile.encoding=UTF-8 -classpath D:JavaProjectJustForTestoutproductionJustForTest GaleShapley
0号男性---0号女性
1号男性---1号女性
2号男性---2号女性

Process finished with exit code 0