In mathematics, economics, and computer science, the Gale-Shapley algorithm (also called the deferred acceptance algorithm or the proposal-rejection algorithm) is an algorithm for finding a solution to a stable matching problem.
Gale–Shapley algorithm From Wikipedia, the free encyclopedia
In the Gale-Shapley algorithm, all partners must be ranked, but a more practical extension is to allow incomplete selection that only rank some of the partners.
This package extends the Gale-Shapley algorithm to allow not only complete selections but incomplete selections.
Check The Go Playground
package main
import (
"fmt"
"github.com/yutohub/matching"
)
func main() {
msPrefers := [][]int{
{0, 1, 2, 3},
{3, 0, 1, 2},
{1, 3, 2, 0},
{0, 2, 3, 1},
}
wsPrefers := [][]int{
{0, 1, 2, 3},
{1, 2, 3, 0},
{0, 3, 2, 1},
{3, 2, 0, 1},
}
result, err := matching.GaleShapley(msPrefers, wsPrefers)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("result")
matching.Show(result)
}
result
m0 --- w0
m1 --- w3
m2 --- w1
m3 --- w2
D. Gusfield and R.W. Irving, The Stable Marriage Problems: Structure and Algorithms, MIT Press, Boston, MA, 1989.