mandated是什么意思dated在线翻译读音例

[python3]稳定匹配算法实现和优化

问题的描述

在这⾥就不赘述了，你能搜到这篇⽂章，那肯定知道只算法的背双双金鹧鸪 景是啥

解决思路

1.男⽣向还未拒绝其的⼥⽣中选出优先级最⾼的，并向其求婚

2.⼥⽣如果没有已经被优先级更⾼的男⽣求婚，则答应（⼥⽣以后可以反悔）。如果反之，则拒绝

3.对此步骤进⾏loop，直到没有求婚发⽣

这篇⽂章，讲⼀个⾃⼰实现的GS算法的版本

⽂章使⽤的代码

上⾯那篇⽂章使⽤的代码是这样的，很清晰。

deffind_stable_matching(man_preferences,woman_preferences):

\"\"\"

Gale-ShapelyAlgorithm

:paramman_preferences:

:paramwoman_preferences:

:return:

\"\"\"

length=len(man_preferences)

is_man_free=[True]*length

is_woman_free=[True]*length

isManProposed=[[Falseforiinrange(length)]forjinrange(length)]

match=[(-1,-1)]*length

whileTrueinis_man_free:

indexM=is_man_(True)

ifFalseinisManProposed[indexM]:

indexW=-1

foriinrange(length):

w=man_preferences[indexM][i]

ifisManProposed[indexM][w]isFalse:

indexW=w

break

isManProposed[indexM][indexW]=True

ifis_woman_free[indexW]isTrue:

is_woman_free[indexW]=False

is_man_free[indexM]=False

match[indexM]=(indexM,indexW)

else:

indexM1=-1

forjinrange(length):

ifmatch[j][1]==indexW:

indexM1=j

break

ifwoman_preferences[indexW].index(indexM)

is_man_free[一日看尽长安花春风得意马蹄疾 indexM1]=True

is_man_free[indexM]=False

match[indexM]=(ind智者乐水仁者乐山怎么读 exM,indexW)

print(match)

returnmatch

这个算法没问题，结果也是对的。但是我认为有点拖沓，还可以进⾏精简。

我们输⼊这样两个⼆维矩阵

MP=[[1,4,3,6,2,5,8,7,9,0],

[2,卖油翁恐怖真相 1,0,3,4,8,5,9,7,6],

[4,3弄花香满衣 ,8,9,0,2,1,7,6,5],

[2,7,6,1,4,3,8,0,9,5],

[5,3,8,4,2,0,7,6,1,9],

[5,0,1,7,2,8,9,4,6,3],

[6,2,9,8,0,7,5,1,4,3],

[9,7,1,8,0,2,5,6,3,4],

[8,0,5,9,6,7,1,2,4,3],

[7,9,1,6,2,0,5,8,4,3]]

WP=[[3,5,0,6,9,4,8,7,2,1],

[0,1,3,2,7,8,5,9,4,6],

[1,0,7,9,3,2,5,8,6,4],

[2,0,6,3,4,1,5,7,9,8],

[5,6,8,3,2,0,9,4,1,7],

[3,0,1,7,9,8,2,4,6,5],

[6,2,7,8,0,9,4,1,5,3],

[9,3,1,2,0,7,5,6,8,4],

[4,1,5,9,6,7,0,2,8,3],

[6,0,1,7,2,9,5,8,4,3]]

上⾯的算法的结果是这样

[(0,1),(1,2),(2,3),(3,4),(4,5),(5,0),(6,6),(7,9),(8,8),(9,7)]

#也就是0号男⽣配1号⼥⽣，以此类推。说实话我觉得结果甚⾄都有些重复。

我的版本

#把⾃⼰带⼊⾮成勿扰录制现场

defgs_matching(man_preferences,woman_preferences):

length=len(man_preferences)

is_man_dated=[False]*length#10位男嘉宾是否已经撩到妹妹了

is_woman_dated=[False]*length#10位美⼈是否已经名花赞美秋天的诗 有主

result=[-1]*length

whileFalseinis_man_dated:

new_man=is_man_(False)

girls_he_likes=愿君笑看千秋尽 man_preferences[new_man]#康康这个男⽣最喜欢谁

forgirlingirls_he_likes:

#查看⼥⽣是否已经被约

if江城梅花引词牌格律 is_woman_dated[girl]isFalse:#发现没有，那就当场拿下

result[new_man]=girl

is_woman_dated[girl]=True

is_man_dated[new_man]=True

break#换下⼀个男嘉宾登场，进⾏选择

else:

#⼥嘉宾已经⼼有所属，现在进⼊权利反转环节，⼥⽣对两位男嘉宾进⾏挑选

current_boyfriend=(girl)

ifwoman_prefere亲近的近义词 nces[girl].index(current_boyfriend)>woman_preferences[girl].index(new_man):

#看看是不是更喜欢新来的这个⼩鲜⾁，如果是，果断甩掉之前的蓝朋友

is_man_dated[current_boyfriend]=False

result[current_boyfriend]=-1

is_man_dated[new_man]=True

result[new_man]=girl

break#换下⼀个男嘉宾登场，进⾏选择

print(result)

我的这个算法的结果是这样的

[1,2,3,4,5,0,6,9,8,7]

#结果数据的index虽然没显⽰出来，但是也代表意义。

#结果数组的第0号位置，就代表0号男⽣配对1号⼥⽣，以此类推。

区别

⾸先说，两个代码都可以正确的运⾏，获得稳定匹配的结果。

但是我的代码使⽤更⼩，更少的变量。

更少的数据交换。

也更符合“延迟接受”算法的含义。