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

package main

import "fmt"

type Person struct {
	name        string
	preferences []string
	partner     *Person
	index       int
}

// 选择更加心仪的男生
func (woman *Person) prefers(man *Person) bool {    
	for _, name := range woman.preferences {
		if name == man.name {  // 遍历到该男生同意该男生的求婚
			return true
		}
		if name == woman.partner.name {  // 当前心仪列表中的男生已经是自己的伴侣，不再考虑新来男生的求婚
			return false
		}
	}
	return false
}

func GaleShapley(men, women []*Person) {
    initiallyFreeMen := make([]*Person, len(men))
	copy(initiallyFreeMen, men)

	for len(initiallyFreeMen) > 0 {
		currentMan := initiallyFreeMen[0]
		currentWomanName := currentMan.preferences[currentMan.index]
		currentWoman := findPersonByName(women, currentWomanName)
		// 严格代码需要判断 currentWoman 是否为 nil

		if currentWoman.partner == nil {
			currentMan.partner = currentWoman
			currentWoman.partner = currentMan
			initiallyFreeMen = removePerson(initiallyFreeMen, currentMan)
		} else if currentWoman.prefers(currentMan) {
			initiallyFreeMen = append(initiallyFreeMen, currentWoman.partner)
			currentMan.partner = currentWoman
			currentWoman.partner = currentMan
			initiallyFreeMen = removePerson(initiallyFreeMen, currentMan)
		} else {
			currentMan.index++
		}
	}
}

func removePerson(people []*Person, person *Person) []*Person {
	index := -1
	for i, p := range people {
		if p == person {
			index = i
			break
		}
	}
	if index == -1 {
		return people
	}
	return append(people[:index], people[index+1:]...)
}

func findPersonByName(people []*Person, name string) *Person {
	for _, person := range people {
		if person.name == name {
			return person
		}
	}
	return nil
}

 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

func main() {
	// 男生： Xavier、Yancey、Zeus
	// 女生： Amy、Bertha、Clare
	// 创建人员列表
	xavier := &Person{
		name:        "Xavier",
		preferences: []string{"Amy", "Bertha", "Clare"},
		partner:     nil,
		index:       0,
	}
	yancey := &Person{
		name:        "Yancey",
		preferences: []string{"Bertha", "Amy", "Clare"},
		partner:     nil,
		index:       0,
	}
	zeus := &Person{
		name:        "Zeus",
		preferences: []string{"Amy", "Bertha", "Clare"},
		partner:     nil,
		index:       0,
	}

	amy := &Person{
		name:        "Amy",
		preferences: []string{"Yancey", "Xavier", "Zeus"},
		partner:     nil,
		index:       0,
	}
	bertha := &Person{
		name:        "Bertha",
		preferences: []string{"Xavier", "Yancey", "Zeus"},
		partner:     nil,
		index:       0,
	}
	clare := &Person{
		name:        "Clare",
		preferences: []string{"Xavier", "Yancey", "Zeus"},
		partner:     nil,
		index:       0,
	}

	men := []*Person{xavier, yancey, zeus}
	women := []*Person{amy, bertha, clare}

	// 运行Gale-Shapley算法
	GaleShapley(men, women)

	// 打印配对结果
	for _, man := range men {
		fmt.Printf("%s -- %s\n", man.name, man.partner.name)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Gale-Shapley
initialize each person to be free
while (some man m is free and hasn't proposed to every woman) do
    w = highest ranked woman in m's list to whom m has not yet proposed
    if (w is free) then
       (m, w) become engaged
    else if (w prefers m to her fiance m') then
       (m, w) become engaged
       m' become free
return the set S of engaged pairs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Gale-Shapley
initialize each person to be free
while (some man m is free and hasn't proposed to every woman) do
    w = highest ranked woman in m's list to whom m has not yet proposed
    if (w is free) then
       (m, w) become engaged
    else if (w prefers m to her fiance m') then
       (m, w) become engaged
       m' become free
return the set S of engaged pairs