python-3.x - Python中连接坐标的排序列表
问题描述
我有一个连接坐标的元组列表(连接的元组数可以是任意的):
[((0, 0), (0, 1)), ((0, 1), (0, 2)), ((0, 2), (0, 3)), ((1, 3), (1, 4)), ((1, 4), (1, 5))]
如何对该列表进行排序,以便删除所有重复项并且我有以下内容:
[((0, 0), (0, 3)), ((1, 3), (1, 5))]
第一个连接坐标:
(0, 0), (0, 1)
(0, 1), (0, 2)
(0, 2), (0, 3)
转向:
(0, 0), (0, 3)
第二个连接坐标:
(1, 3), (1, 4)
(1, 4), (1, 5)
转向:
(1, 3), (1, 5)
我曾想过枚举列表:
for index, item in enumerate(coordinates):
if item[index] == item[index + 1]:
...
但通常甚至不知道如何解决这个问题。
解决方案
算法:
- 从一个空列表开始
- 在其中添加一个空列表
迭代你的元组:
- 如果结果列表中的最后一个列表为空,则将当前元组的所有元素添加到其中
- 如果结果列表的最后一个列表中的最后一个元素与您当前的元组第一个元素相同:
- 要么将您当前的元组最后一个元素添加到它
- 或将其最后一个元素替换为当前项目的最后一个元素
- 如果没有,请在结果列表中添加一个新的空列表并将当前元组的所有元素添加到其中
- 继续迭代直到完成
如果您选择以上任何一种:
完成后,优化您的结果:并将每个内部列表第一个和最后一个元素添加到一个新列表中,并将该列表添加到您的最终结果列表中。
代码:
data = [((0, 0), (0, 1)), ((0, 1), (0, 2)), ((0, 2), (0, 3)),
((1, 3), (1, 4)), ((1, 4), (1, 5))]
result = [[]]
for connect in data:
# empty, add all
if not result[-1]:
result[-1].extend(connect)
continue
# does not continue current streak
if result[-1][-1] != connect[0]:
result.append([c for c in connect])
# does continue current streak
else:
# to collect all intermediate steps as well
result[-1].append(connect[1])
# if you do not need to build the whole thing, use this instead:
# result[-1][-1] = connect[1]
# simplify result
r = [ (r[0],r[-1]) for r in result]
print(result, r , sep="\n")
输出:
[[(0, 0), (0, 1), (0, 2), (0, 3)], [(1, 3), (1, 4), (1, 5)]]
[((0, 0), (0, 3)), ((1, 3), (1, 5))]
如果在继续连胜时替换内部列表的最后一个元素,您可以避免最后的细化步骤,但您失去了在第一个结果列表中查看整个连接性的能力。