最大排列问题的算法实现

Python

算法需求如下:

有八个人对应分配了八个位置,但是其中一些人对自己的位置并不满意,问在最多人满意的情况下,最后调换位置的有哪几个?人物对应喜好如下图:

图例:(A和B都喜欢C位,但是分配到的分别是A位和B位)

思路:

如果拿到问题,我们首先对于问题做一个分析:对于要求满意的人尽可能多,也就是调换位置的人尽可能多,求调换位置的有多少,那我们可以换个思路,不调换位置的有多少,假如说它本身就在自己喜欢的位置,那么他不用调换位置,如果两个人刚好喜欢对方喜欢的位置,那么可以互换,剩下的如果还有人喜欢那个位置,那么这个人就要被淘汰,比如上图的A和B和C,A和B都喜欢C位而C喜欢A位,那么如果把A淘汰,那么C的位置就得不到满足(A被淘汰意味着A就坐在A位),那么如果淘汰B,看起来是个正确的选择,因为C可以和A互换,得到都满意的结果。

知道了需要 剔除那些元素,下面开始实现这个算法。

先用一个列表表示人物的位置关系

U = 【2,2,0,5,3,5,7,4】

前两个元素都想在第二个位置

U【1】=U【2】=1

首先,通过观察我们发现,对于一般的位置而言,我们有两个输入的都会删除其中一个,比如A和B,那么先贴代码:

创建一个长度为8的列表,记录位置,然后一个全部为0的列表用来记录对应的输入,比如第三个位置有两个输入就记为2,那么我们得到一个记录入边数目的列表为[1,0,2,1,1,2,0,1]

也就是代码中的count(计数器)

Q是为了记录count中为0的元素对应的在A中的元素,也就是没有入边的位置,没人喜欢的位置,直接删除,也就是{1,6},从图中可以看出,第2个位置和第7个位置没人想坐(没有边输入)故直接淘汰

接着进入while循环,将栈中顶部元素弹出,也就是6,将6对应的A中的元素也删除,因为这个人和这个位置是绑定的,位置没了,人也就被淘汰了,他只能坐6号了。

接着获取M列表中对应的第i个元素获取对应元素,如果这个元素入边数目为1,那么这个就是下一个要删除的对象,因为没了i ,就一个入边也没了,以此推下去,我在代码中顺便打印了对应弹栈出来的元素,方便学习。

欢迎交流

QQ:2533524298

编辑于 2018-07-21

此条目发表在算法分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注