python - 通过切断循环来缩短元组列表？

Question

我有一个生成元组列表的函数，例如:

[(0, 0), (1, 1), (1, 2), (1,3), (2, 4), (3, 5), (4, 5)]

它们用于表示我正在制作的游戏中的图 block (行、列)路径。

我用来生成这些路径的函数并不完美，因为它经常会产生“循环”，如下所示:

[(2, 0), (2, 1), (1, 2), (0, 3), (0, 4), (1, 5), (2, 5), (3, 4), (3, 3),
 (3, 2), (4, 1)]

上面的路径应该是这样的:

[(2, 0), (2, 1), (3, 2), (4, 1)]

这些路径可以包含任意数量的循环，循环可以是任意大小和形状。

所以我的问题是，我如何在 python 中编写一个函数来剪切循环列表并返回一个没有这些循环的新的、更短的列表。

我的尝试如下:

def Cut_Out_Loops(Path):

    NewList = list(Path)
    Cutting = True

    a = 0
    for Cords in Path:
        a += 1

        try:
            for i in range(a + 2, len(Path)):
                if (Path[i][0] == Cords[0] and abs(Path[i][1] - Cords[1]) == 1:
                    NewList = NewList[0:a] + NewList[i:]
                    Path = list(NewList)
                elif Path[i][1] == Cords[1] and abs(Path[i][0] - Cords[0]) == 1:
                    NewList = NewList[0:a] + NewList[i:]
                    Path = list(NewList)
                elif abs(Path[i][0] - Cords[0]) == 1 and abs(Path[i][1] - Cords[1]) == 1:
                    NewList = NewList[0:a] + NewList[i:]
                    Path = list(NewList)
                elif abs(Path[i][1] - Cords[1]) == 1 and abs(Path[i][0] - Cords[0]) == 1:
                    NewList = NewList[0:a] + NewList[i:]
                    Path = list(NewList)
                Cutting = False
        except IndexError:
            Cutting = True

Answer 1

虽然你对“循环”的定义不是很清楚，试试这个

def clean(path):
    path1 = []
    for (x1,y1) in path:
        for (i,(x2,y2)) in enumerate(path1[:-1]):
            if abs(x1-x2) <= 1 and abs(y1-y2) <= 1:
                path1 = path1[:i+1]
                break
        path1.append((x1,y1))
    return path1

它绝对适用于您的示例:

 >>> path = [(2, 0), (2, 1), (1, 2), (0, 3), (0, 4), (1, 5), (2, 5), (3, 4), (3, 3), (3, 2), (4, 1)]
 >>> clean(path)
 [(2, 0), (2, 1), (3, 2), (4, 1)]

也就是说，它只是最直接的蛮力解决方案。复杂度是二次方的。