Python 删除 for 循环中的数组项

Question

我正在尝试根据彼此之间的距离删除数组中的一些项目。

我在一个元组数组中有 104 项:

points = [(910, 28), (914, 29), (919, 30), (915, 32), (766, 73), (777, 75), (768, 80), (1227, 117), (1224, 119), (1228, 120), (1224, 121), (1228, 122), (1221, 124), (1218, 126), (486, 147), (482, 150), (474, 153), (905, 182), (908, 184), (904, 186), (901, 187), (913, 188), (909, 190), (903, 193), (187, 213), (186, 214), (189, 215), (611, 262), (617, 264), (619, 265), (610, 268), (1231, 272), (1228, 274), (1228, 276), (1232, 278), (1223, 282), (486, 306), (477, 309), (463, 312), (470, 313), (486, 315), (473, 319), (764, 376), (773, 379), (770, 383), (795, 386), (778, 390), (631, 412), (626, 414), (624, 416), (626, 418), (1218, 434), (1217, 435), (1218, 436), (1219, 437), (1220, 438), (1222, 439), (1225, 440), (1226, 442), (480, 460), (478, 463), (1071, 466), (1062, 468), (1067, 469), (1072, 470), (339, 485), (343, 487), (345, 489), (346, 490), (350, 492), (343, 495), (352, 497), (930, 505), (929, 508), (929, 513), (199, 535), (197, 537), (203, 539), (201, 542), (771, 547), (774, 547), (773, 548), (772, 549), (776, 549), (776, 550), (629, 576), (628, 579), (631, 580), (625, 583), (1237, 586), (1218, 590), (1226, 593), (1223, 595), (1227, 599), (639, 732), (643, 733), (643, 734), (204, 875), (209, 877), (210, 879), (210, 880), (210, 882), (210, 884), (204, 887)]

我的代码如下:

print len(points)
w = 152
h = 157
for pt in points:
    for fpt in points:
        if pt == fpt:
            continue
        else:
            distX = abs(pt[0] - fpt[0])
            distY = abs(pt[1] - fpt[1])
            dist = distX + distY
            if distX < w / 2 and distY < h / 2:
                points.remove(fpt)

print len(points)

当我运行它时，它会删除很多项目，只给我留下 33，但这是不正确的。如果我再次运行它，它会给我留下正确的数字，即 22。

我确定我做错了什么，谁能帮我定位并改正我的错误？

Answer 1

在迭代列表时就地删除列表项不是好的做法。例如，

if points has only 3 elements [a, b, c], 
a is adjacent to b, 
b is adjacent to c, 
but a is not adjacent to c, 
Correct result is [a] after the algorithm runs. But with your algorithm,
after the first iteration, b is removed; points = [a, c]
c can never be removed, since a and c are not adjacent.

你要找的是一个 Union-find-set，这里是一个实现: http://code.activestate.com/recipes/215912-union-find-data-structure/

下面是一个更简单的 Union-Find 实现，供您引用: A set union find algorithm