GaleShapley算法稳定性检验

Question

我是python编码的初学者，我正试图找出如何测试Gale-Shapley算法的稳定性。我理解，对于一对稳定的伴侣来说，这意味着不存在两个人比他们指定的伴侣更喜欢对方的情况

参与者偏好数据如下：

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]]

例如，对于偏好[0]，男孩1对女孩1的排名是1，女孩2是3，女孩3是2，女孩4是4。这意味着名单是这样的：[“男孩1”，（女孩1的排名），（女孩2的排名），（女孩3的排名），（女孩4的排名）]

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

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

我试图提出一个函数，在给定偏好、解和偶数的情况下，如果解是稳定的，则产生true，如果解是不稳定的，则产生false

我尝试过使用pandas和numpy，但我一直遇到许多for循环和if以及索引问题，因为我对这些python库都不太熟悉。我现在试着回到基础，看看是否有可能做到这一点。然而，当我这么做的时候，我意识到我一直在使用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

Answer 1

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

该算法在^{} package中实现

最后，我要指出，使用由字符串和整数组成的列表有点令人困惑。我建议区分男性对女性和女性对男性的偏好，例如：

female_prefs = {1: [2, 1, 3, 4], 2: [4, 3, 2, 1], 3: [1, 2, 3, 4], 4: [3, 4, 2, 1]}