Gale-Shapley算法

package main

import "fmt"

type people struct {
  Name       string // 名字
  LikePeople string // 喜欢的人名
}

type lovers struct {
  Boy  people
  Girl people
}

func main() {
  // 分别构造男女队列
  boyArr := []people{}
  girlArr := []people{}
  // 分别对他们进行匹配
  var result []lovers
  for _, boy := range boyArr {
    // 查看他喜欢的女孩是否喜欢他
    for _, girl := range girlArr {
      if boy.LikePeople == girl.Name {
        // 两情相悦了
        if girl.LikePeople == boy.Name {
          result = append(result, lovers{
            Boy:  boy,
            Girl: girl,
          })
        }
        break
      }
    }
  }
  fmt.Println(result)
}

package main

type people struct {
  Name        string   // 名字
  LikePeople  []string // 喜好列表
  CurrentLike int      // 后面算法记录当前表白对象时使用
  Friend      string   // 当前匹配对象
}

func main() {
  // 分别构造男女队列
  boyArr := []*people{}
  girlArr := []*people{}
  for true {
    // 找到一个没有对象, 且未全部表白的男生
    var searchBoy *people
    for _, boy := range boyArr {
      if boy.Friend != "" { // 当前男孩已经有对象了
        continue
      }
      // 男孩向所有女生表白过了
      if boy.CurrentLike >= len(boy.LikePeople) {
        continue
      }
      searchBoy = boy
      break
    }
    if searchBoy == nil { // 已经全部有对象了, 结束
      break
    }
    // 男生向女生依次表白
    var i int
    for i := searchBoy.CurrentLike; i < len(searchBoy.LikePeople); i++ {
      girlName := searchBoy.LikePeople[i]
      // 找到这个女孩
      girl := searchPeople(girlArr, girlName)
      if girl == nil { // 习惯了, 判下空
        continue
      }
      if girl.Friend == "" { // 若女孩没有对象, 则直接配对
        girl.Friend = searchBoy.Name
        searchBoy.Friend = girl.Name
        break
      } else { // 若女孩有对象, 看下 girl 更喜欢谁
        searchBoyIdx := searchNameIndex(girl.LikePeople, searchBoy.Name)
        girlFriendIdx := searchNameIndex(girl.LikePeople, girl.Friend)
        if girlFriendIdx < searchBoyIdx { // 保持当前
          continue
        } else { // 重新组队
          girlFriend := searchPeople(boyArr, girl.Friend)
          if girlFriend != nil { // 分手了
            girlFriend.Friend = ""
          }
          girl.Friend = searchBoy.Name
          searchBoy.Friend = girl.Name
        }
      }
    }
    searchBoy.CurrentLike = i
  }
}

func searchPeople(peopleArr []*people, name string) *people {
  for _, people := range peopleArr {
    if people.Name == name {
      return people
    }
  }
  return nil
}

func searchNameIndex(nameArr []string, name string) int {
  for i, tmpName := range nameArr {
    if tmpName == name {
      return i
    }
  }
  return -1
}