python - 如何解决排序和组合问题

问题描述

我正在尝试组合四个一行两列的列表，例如line_parts=[[2, 1], [2, 0], [1, 2], [5, 2]]，以创建一行五列的列表，例如all_lines=[[5, 2, 1, 2, 0]]. 但是，四个 1 行 2 列列表的列表写为line_parts=[[2, 1], [2, 0], [1, 2], [5, 2]]，但我想将其设为 1 行 5 列列表，即使它是[[2, 1], [1, 2], [2, 0], [5, 2]]、[[2, 1], [1, 2], [5, 2], [2, 0]]、[[1, 2], [5, 2], [2, 0], [2, 1]]等。

目前，我可以为[[5, 2, 1, 2, 0]]from创建一个单行五列的列表line_parts=[[2, 1], [2, 0], [1, 2], [5, 2]]。

line_parts=[[2, 1], [2, 0], [1, 2], [5, 2]]

lines = []
for i,j in line_parts:
    if i == 5:
        path = [ int(i), j ]
        line_parts.remove(line_parts[line_parts.index([i,j])])
        while len(path) != len(line_parts) + 2:
            if path[-1] == 0:
                del path[-1]
                line_parts.insert(len(line_parts),line_parts[0])
                line_parts.remove(line_parts[0])
            else:
                line_parts.insert(len(line_parts),line_parts[0])
                line_parts.remove(line_parts[0])
                while path[-1] != 0:
                    line_parts.insert(len(line_parts),line_parts[0])
                    line_parts.remove(line_parts[0])
                    for m, n in line_parts:
                        if m == path[-1]:
                            path.append(n)
                            break
        lines.append(path)
all_lines=lines

print("all_lines:",all_lines)

运行上述程序的结果如下

all_lines: [[5, 2, 1, 2, 0]]

但是，当我更改line_parts=[[2, 1], [2, 0], [1, 2], [5, 2]]为line_parts=[[2, 1], [1, 2], [2, 0], [5, 2]]时，会发生无限循环，并且我没有得到像[[5, 2, 1, 2, 0]]. 我试图改进它，但它不断重复，一种模式输出一个单行五列的列表，如 [[5, 2, 1, 2, 0]]，但另一种模式不起作用。

您能否给我一些关于如何改进程序的提示或建议，以便我在所有情况下都能得到一个单行五列的列表，不仅仅是[[2, 1], [2, 0], [1, 2], [5, 2]], [[2, 1], [1, 2], [2, 0], [5, 2]], [[2, 1], [1, 2], [5, 2], [2, 0]],[[1, 2], [5, 2], [2, 0], [2, 1]]等？

先感谢您。

【补充说明】</p>

这是逻辑。对不起，我通过包含循环过程使其不那么简洁。

[[2, 1], [2, 0], [1, 2], [5, 2]] 可以按字母形式表示为 [[b, c], [b, d], [c, b] , [a, b]]。在这个问题的背景下，我们想一次从 a 移动到 d，我们可以将 b 和 c 视为 a 和 d 之间的中转点。

在中包含的列表中[[b, c], [b, d], [c, b], [a, b]]，如果存在带有 at 的列表，则根据该列表index 0中的元素定义路径。（当查找带有 at 的列表时，从列表顶部开始。） ⇒结果是。index 0index 1index 0path=[a,b]
[a, b]从列表中删除元素[[b, c], [b, d], [c, b], [a, b]]。⇒<code>[[b, c], [b, d], [c, b], [a, b]] 变成[[b, c], [b, d], [c, b]].
path 中的元素数不等于[[b, c], [b, d], [c, b]]plus中的列表数2，因此（第一个）while 循环继续进行。⇒路径中的元素个数是3，后者是5，所以它们不相等。
由于path=[a,b]is not的结尾，d带有index 0in的元素[[b, c], [b, d], [c, b]]被移动到列表的末尾，带有的元素index 0从列表中移除。⇒结果[[b, c], [b, d], [c, b]]是[[b, d], [c, b],[b, c]]。
路径不以结束d，因此（第二个）while 循环继续。
将带有index 0in的元素移动[[b, d], [c, b],[b, c]]到列表的末尾，并从列表中删除（带有的元素index 0）。⇒结果[[b, d], [c, b],[b, c]]是[[c, b],[b, c],[b, d]]。
在包围的列表中[[c, b],[b, c],[b, d]]，如果有一个列表带有b（末尾的元素path=[a,b]） at index 0，则将该列表的元素添加index 1到路径的末尾。（查找带有的列表时d，从列表顶部开始。） ⇒结果是path=[a,b,c]。
由于路径的结尾不是d，继续（第二个）while 循环。
将带有index 0in的元素移动[[c, b],[b, c],[b, d]]到列表末尾，并从列表中删除带有 in 的元素index 0。⇒结果[[c, b],[b, c],[b, d]]是[[b, c],[b, d],[c, b]]。
在中包含的列表中[[b, c],[b, d],[c, b]]，如果有一个带有cat的列表index 0（位于末尾的path=[a,b,c]元素），则将该列表的元素添加index 1到路径的末尾。（查找带有的a列表时c，从列表顶部开始。） ⇒结果是path=[a,b,c,b]。
由于 path 的结尾不是d，因此（第二个）while 循环继续进行。
index 0带有in的元素[[b, c],[b, d],[c, b]]被移动到列表的末尾，并且（索引为 0 的元素）从列表中删除。⇒结果[[b, c],[b, d],[c, b]]是[[b, d],[c, b],[b, c]]。
在中包含的列表中[[b, d],[c, b],[b, c]]，如果有一个列表b（的最后一个元素path=[a,b,c,b]） at index 0，则将该列表的元素 at 添加index 1到路径的末尾。（查找带有的列表时b，从列表顶部开始。） ⇒结果是path=[a,b,c,b,d]。
退出（第二个）while 循环，因为路径的结尾是d.
path 的元素个数和[[b, d],[c, b],[b, c]]plus2中包含的列表个数相等，所以我们退出（第一个）while 循环。⇒路径中的元素个数为5，后者也等于5。
添加行的路径。⇒结果是lines=[[a,b,c,b,d]]。
从all_lines=lines，我们得到all_lines=[[a,b,c,b,d]]。

算法到此结束。

非常感谢您阅读到最后。我将非常感谢您的意见。如果有什么需要补充的，请告诉我。

标签： python

解决方案

作为免责声明，我真的不擅长你的问题所涵盖的每个主题：图形、算法和递归。但没有人回答，这是一个很好的练习

这里有两个问题需要考虑：您的示例所暗示的具体问题（5 个节点 4 个边，我认为这些话是对的？），以及如何解决更普遍的问题（我认为这就是您的代码试图做的）。

解决“24”有点容易：根据定义，您已经知道五个节点中的 4 个。你只需要找到中间的那个

def get_simple_path(lst):
    # flatten the list to make it easier to find max/min
    flat=[y for x in lst for y in x]
    result=[0]*5
    
    # first two and last two are found easily:
    # the max pair
    a=max(flat)
    result[0]=a
    for pair in lst:
        if pair[0]==a:
            result[1]=pair[1]
            lst.remove(pair)
    
    # the min pair
    d=min(flat)
    result[-1]=d
    for pair in lst:
        if pair[1]==d:
            result[-2]=pair[0]
            lst.remove(pair)
    
    # we're left with only two lists [ab, ba] or [ba, ab]
    # if a matches result[1], then result[2] is b, else it's a
    if result[1]==lst[0][0]:
        result[2]=lst[0][1]
    else:
        result[2]=lst[0][0]
    return result

它适用于 24 种排列，不需要任何 while 循环

现在对于更通用的解决方案，我们需要递归（至少我这样做）。您的版本不起作用，因为当它失败时，它无法恢复它仍然可以工作的状态（回溯？）。

def get_path(lst, left_val, res=[]):
    pairs=[]
    for i, pair in enumerate(lst):
        if pair[0]==left_val:
            pairs.append(pair)
    if pairs:
        for pair in pairs:
            lst2=lst.copy()
            lst2.remove(pair)
            res2=res.copy()
            res2.append(pair[0])
            if z:=get_path(lst2, pair[1], res2):
                return z
    elif not pairs and lst==[]:
        res.append(left_val)
        return res

初始化递归，left_val是列表的最大值

如果我尝试使用[[5, 8], [1, 6], [6, 7], [8, 0], [7, 3], [4, 1], [10, 6], [3, 4], [6, 5]]它的 362880 排列，我总是会得到[10, 6, 7, 3, 4, 1, 6, 5, 8, 0]

python - 如何解决排序和组合问题

问题描述

解决方案

推荐阅读