python – 为最大成对匹配排序数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 为最大成对匹配排序数组，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4127字，纯文字阅读大概需要6分钟。
内容图文
我有一个数组：
array([[ 4, 10],
[ 4, 2],
[ 0, 7],
[ 5, 11],
[ 6, 8],
[ 3, 6],
[ 9, 7],
[ 2, 11],
[ 9, 5],
[ 8, 1]])
我想要一种方法来对值对进行排序,以便尽可能多的成对2元素集具有公共值.这是所需有序数组的示例：
array([[ 4, 10],
[ 4, 2],
[ 2, 11],
[ 5, 11],
[ 9, 5],
[ 9, 7],
[ 0, 7], #note the gap here:
[ 8, 1],
[ 6, 8],
[ 3, 6]])
关于这些阵列有几个条件.没有重复对(即：[1,0]或[0,1]将出现在数组的其他位置,如果[0,1]已经存在).没有对具有相同的值(即：[1,1]将不存在).没有对将有两个以上的匹配(喵：在整个数组中没有值超过两次.)但是一对可以有零匹配(注意在上面的数组中没有匹配的间隙).
显然,我可以创建数组的每个排列,但这似乎是野蛮的.我认为可能有某种方法可以切割平台并以合理的方式重新堆叠,以便在少量切割中进行分类.但在我走这条路之前,我想：1)确保没有numpy或集合功能已经做到了这一点. 2)知道没有棘手的天才方式来使用numpy .sort()(或类似的)来做到这一点. 3)确定这是否是一项常见任务,并且有算法可以执行此操作. (“哦,这是Blumen-Funke算法！”)
下面是一些生成混洗测试数组并检查已排序数组的代码：
def shuffled(N=12, ans=1):
'''returns is now the unsorted test array'''
r = range(N)
random.shuffle(r)
l = []
for i in range(N):
l.append((r[i-1], r[i]))
random.shuffle(l)
return np.array(l)[ans+1:]
# step 2: ???
def test_ordered(a):
'''checks if generated array has been sorted'''
c0 = a[1:,0]==a[:-1,0]
c1 = a[1:,0]==a[:-1,1]
c2 = a[1:,1]==a[:-1,0]
c3 = a[1:,1]==a[:-1,1]
cond = c0+c1+c2+c3
ans = sum(numpy.logical_not(cond))
# when sorted this should return the same number input into
# shuffled() as 'ans':
return ans
(这是一个主观问题吗？我被警告说是.)
结果：
非常感谢您的帮助. Sven的解决方案比Paul的解决速度快20％,并且很高兴,他们都在线性时间运行,Doug的答案并没有解决问题.在输入数据中,性能??对“中断”或“间隙”的数量存在很高但也很大程度上线性的依赖性.见下图. 10,000幅度轴是N. 0.5轴是断裂的百分比. z轴是以秒为单位的性能.
再次感谢！
解决方法:
您已经描述了一个图形,其中顶点是数字,边缘是您的对.
您的条件指定每个数字在列表中显示一次或两次.这意味着图表中的连接组件是线(或循环).您可以使用此算法找到它们：
> [Line exists]如果可能,选择一个1度的数字(也就是说,它只在列表中出现一次).尽可能地跟随对的链,将它们添加到输出并从图中移除遍历的顶点.
> [循环存在]如果没有度数为1的数字,则表示所有组件都是循环.选择任何顶点(它将具有2级).像以前一样跟踪对,将它们添加到输出并删除遍历的顶点,但是这次在达到原始数字时停止.
>重复,直到用完图中的所有顶点.
您可以有效地运行此算法：维护一组1度的顶点和2度的另一个顶点.当您使用边(原始列表中的一对)时,适当地修改集：从第一个集中删除1级的端点,并将端点从2级设置移动到1级.或者,使用优先级队列.
您还需要对配对进行有效查找：从顶点到相邻顶点列表构建一个dict.
使用这些想法,您可以在线性时间内找到最佳排序(假设O(1)set和dict实现).
这是一个有点笨重的实现.
import collections
def handle_vertex(v, vs):
if v in vs[0]:
vs[0].remove(v)
elif v in vs[1]:
vs[0].add(v)
vs[1].remove(v)
def follow(edgemap, start, vs):
"""Follow a path in the graph, yielding the edges."""
v0 = start
last = None
while True:
# All vertices that we can go to next.
next_v = [v for v in edgemap[v0] if v != last]
if not next_v:
# We've reached the end (we must have been a line).
return
assert len(next_v) == 1 or (v0 == start and len(next_v) == 2)
next_v = next_v[0]
# Remove the endpoints from the vertex-degree sets.
handle_vertex(v0, vs)
handle_vertex(next_v, vs)
yield v0, next_v
if next_v == start:
# We've got back to the start (we must have been a cycle).
return
v0, last = next_v, v0
def pairsort(edges):
edgemap = collections.defaultdict(list)
original_edges = {}
for a, b in edges:
# Build the adjacency table.
edgemap[a].append(b)
edgemap[b].append(a)
# Keep a map to remember the original order pairs appeared in
# so we can output edges correctly no matter which way round
# we store them.
original_edges[a, b] = [a, b]
original_edges[b, a] = [a, b]
# Build sets of degree 1 and degree 2 vertices.
vs = [set(), set()]
for k, v in edgemap.iteritems():
vs[len(v) - 1].add(k)
# Find all components that are lines.
while vs[0]:
v0 = vs[0].pop()
for e in follow(edgemap, v0, vs):
yield original_edges[e]
# Find all components that are cycles.
while vs[1]:
v0 = vs[1].pop()
for e in follow(edgemap, v0, vs):
yield original_edges[e]
input = [
[ 4, 10],
[ 4, 2],
[ 0, 7],
[ 5, 11],
[ 6, 8],
[ 3, 6],
[ 9, 7],
[ 2, 11],
[ 9, 5],
[ 8, 1]]
print list(pairsort(input))
内容总结
以上是互联网集市为您收集整理的python – 为最大成对匹配排序数组全部内容，希望文章能够帮你解决python – 为最大成对匹配排序数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。