0

我是 python 编码的初学者，正在尝试弄清楚如何测试 Gale-Shapley 算法的稳定性。我知道，要进行稳定的配对，这意味着不会有 2 个人比指定的伴侣更喜欢对方。

参与者的偏好数据如下：

preference = [["boy1",1,3,2,4], ["boy2",1,2,4,3],["boy3",1,2,3,4],["boy4",2,3,1,4],["girl1",2,1,3,4],["girl2",4,3,2,1],["girl3",1,2,3,4],["girl4",3,4,2,1]]

例如，对于preference[0]，boy1 对girl1 的排名是1，girl2 是3，girl3 是2，girl 4 是4。这意味着列表是：[“boy1”，（girl1 的排名），（排名女孩2），（女孩3的排名），（女孩4的排名）]。

配对解决方案的示例如下：

solution1 = [["boy1","girl1"],["boy2","girl3"],["boy3","girl2"],["boy4","girl4"]

考虑到偏好、解决方案和配对的数量，我正在尝试提出一个函数，如果解决方案稳定则产生 true，如果解决方案不稳定则产生 false。

我尝试过使用 pandas 和 numpy，但由于我对这些 python 库中的任何一个都不是很熟悉，所以我一直被许多 for 循环和 if 和索引问题所困扰。我现在正试图回到基本，看看是否有可能做到这一点。然而，当我这样做时，我意识到我一直在使用 for 循环，它不会那么有效。以下是我的不完整代码，请就我应该做些什么来提高这个不完整代码的效率提出建议 - 以及一旦它完成后是否可以执行我当前的不完整代码。请建议我也可以使用的任何python库，非常感谢任何建议！

def teststability(n, preference, solution):
  for i in solution[i]:
    fpo = solution[i][1][1]
    for j in preference[j]:
      if solution[i][0] == preference[j][0]:
        rank = preference[j][fpo]
        if rank == 1:
          continue
        else:
          for k in pref[j][k]:
            if pref[j][k] < rank:
              lst.append("girl"+str(k))
            else:
              continue
4

1 回答 1

0

你不需要 Pandas 或 Numpy，因为这是一个经典的算法 SAT 问题，而不是数据问题。（如果您需要将给定的解决方案算法应用于大量对数组，那么 Pandas 可能会很有用。）

该算法在QuantEcon/MatchingMarkets包中实现。

最后，我注意到您使用由字符串和整数组成的列表有点令人困惑。我建议对男性对女性和女性对男性的偏好进行判断，例如：

female_prefs = {1: [2, 1, 3, 4], 2: [4, 3, 2, 1], 3: [1, 2, 3, 4], 4: [3, 4, 2, 1]}
于 2020-02-23T13:26:59.120 回答