Python列表中的特定路径组合或排列 [英] Python list of lists specific path combinations or permutations

问题描述

我有一个列表列表，我正在寻找类似于组合或排列的东西，但有些条件可能导致良好的Path或Dead_End。如果是Dead_End，它应该索引到列表中的下一个选项。
示例：

I have a list of lists and am looking for something similar to combinations or permutations, but there are conditions that may result in good "Path" or "Dead_End". If "Dead_End", it should index to the next choice in the list. Example:

AList = [[1, 2, 3],
         [2, 0, 3],
         [3, 1, 0],
         [1, 0, 2]]

N = 0
Index = 0
#AList[N][Index]=1,  AList[2][2]=0

我会喜欢从值AList [N] [Index]开始，它在开始时是[0] [0]因此等于1并将其分配给N.在N被赋值为1之后，我们永远不能回到那个列表并且Path = [1]。

I would like to start with the value AList[N][Index], which at the start is [0][0] and therefore equals 1 and assign that to N. After N is assigned 1, we can never go back to that List and the Path = [1].

然后我会有AList [N] [Index]，这是AList [1] [0]并等于2.分配到N. Path.append（N）我会有Path = [1,2]。

Then I would have AList[N][Index], which is AList[1][0] and that equals 2. Assign that to N. Path.append(N) and I would have Path = [1, 2].

AList [N] [Index]接下来会等于3，N = 3，Path将变为[1,2,3]

AList[N][Index] would next equal 3, N = 3, and Path would become [1, 2, 3]

现在AList [N] [Index]等于1.这将是一个Dead_Path而不是一个好的解决方案因为1已经在Path中，我们无法再回到它。所以我想索引到列表中的下一个选项。 Index = Index + 1.这将导致AList [N] [Index] = 0. Path = [1,2,3,0]

Now AList[N][Index] would equal 1. This would be a Dead_Path and not a good solution because 1 is already in Path and we can't go back to it. So I want to index over to the next choice in the list. Index = Index + 1. That would result in AList[N][Index] = 0. Path = [1, 2, 3, 0]

这是一个好的路径和许多好路径和许多Dead_Ends。例如，另一个好的Path将是Path = [1,0,2,3]。

That is a good Path and there are many good Paths and many Dead_Ends. For example, another good Path would be Path = [1, 0, 2, 3].

这是一个多嵌套的IF，For，While循环场景还是有一个itertools函数来测试所有的Paths和Dead_Ends？并且列表列表可能更复杂并且不均匀以创建更多Dead_Ends，例如：

Is this a multi-nested IF, For, While loop scenario or is there an itertools function to test out all of the Paths and Dead_Ends? And the List of list could be more complicated and not uniform to create even more Dead_Ends, like:

BList = [[1, 4, 3],
         [2, 0, 3, 4],
         [3, 4, 0],
         [1, 2],
         [3, 2, 1, 0]]

编辑：
我无法处理所有Dead_Ends 。所有的循环和索引让我感到困惑，所以我认为最好的解决方案是我使用itertools并列出所有路径组合并允许重新访问上一个节点。然后我将使用set（）函数来消除重新访问节点的列表。最后，我留下了Perfect_Paths，每次点击每个节点。我不知道这是否是最快/最干净的，但它确实有效。代码如下：

Edited: I couldn't deal with all of the Dead_Ends. All of the loops and indexing got me confused, so I think the best solution is that I use itertools and list all path combinations and allow revisiting back to previous node. Then I would use set() function to eliminate the lists that revisited a node. In the end, I'm left with Perfect_Paths hitting each node once. I don't know if this is the fastest / cleanest, but it worked. Code below:

Perfect_Path = list()
i = 0 

All_Paths = list(itertools.product(*Alist))

for i in range(len(All_Paths)):
    if len(set(All_Paths[i])) == len(Alist):  #filter out paths that revisited a node, which means it would have same number repeated in list
        Perfect_Path.append(All_Paths[i])

print ("The perfect paths are ", Perfect_Path)

编辑：我上面的代码适用于小型Alist，但迭代所有组合稍微大一点列表，说10个数据节点突然变成数百万个路径。然后我必须设置（）它们以消除选择。回到我的绘图板。

Well my code above works for a small Alist, but to itertools all combinations for a slightly larger list, say 10 data nodes all of a sudden becomes millions of paths. And then I have to set() them to eliminate choices. Back to the drawing board for me.

推荐答案

一遍又一遍地阅读问题的文本我发现了两个规则变体找到正确的答案，并在这里提供他们两个，而不是询问哪一个是OP想到的问题。

Reading through the text of the question again and again I detected two variants of rules for finding the right answer and will provide here both of them without asking which one is the one OP had in mind asking the question.

让我们从简单的开始吧。通过矩阵元素的路径可以从一个元素跳转到任何其他元素，并且路径的唯一限制是允许的路径中没有相同的值。这使得通过矩阵的值找到所有路径变得非常容易，如下所示：

Let's start with the easy one. The path through the elements of the matrix can jump from one element to any other element and the only restriction for the path is that there are no same values in the path allowed. This makes it very easy to find all paths through the values of the matrix and it goes as follows:

步骤1：使用平面设置的所有矩阵值唯一值

Step1: make out of all of the matrix values a flat set with unique values

第2步：创建此集合的所有可能排列

Step2: create all possible permutations of this set

让我们用代码演示此变体是否有效在一个相当大的矩阵上：

Let's demonstrate with code that this variant works even on a quite large matrix:

theMatrix = [[1, 1, 3, 2, 1, 3, 3, 3, 2, 1, 1, 3],
             [1, 2, 1],
             [2, 3, 3, 1, 3, 3, 2, 1, 1, 1, 3, 3, 1, 3, 3],
             [3, 1, 3, 1, 2],
             [2, 3, 3, 1, 3, 3, 2, 1, 1, 1, 3],
             [1, 2],
             [1, 2, 1],
             [2, 3, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 3],
             [3, 1, 3, 1, 2],
             [2, 3, 3, 1, 3, 3, 2, 1, 1, 1, 3],
             [1, 2],
             [2, 3, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 3],
             [3, 1, 3, 1, 2],
             [2, 3, 3, 1, 3, 3, 2, 1, 1, 1, 3],
             [3, 2, 1, 3, 1]]
setOnlyDifferentMatrixValues = set()
for row in range(len(theMatrix)):
    for column in range(len(theMatrix[row])):
        setOnlyDifferentMatrixValues.add(theMatrix[row][column])
from itertools import permutations
allPossiblePaths = permutations(setOnlyDifferentMatrixValues)
print(list(allPossiblePaths))

上面的代码输出：

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

现在是具有更多代码行的更复杂的变体。代码是必要的，因为那里有更多限制，路径只能通过邻居的矩阵元素（水平，垂直和对角线）。在这种情况下，并非所有路径都具有相同的长度和相同的元素：

Now the more complex variant with more lines of code. The code is necessary, because there are more restrictions there and the path can go only through matrix elements which are neighbors (horizontal, vertical and diagonal). In this case not all paths have the same length and the same elements in them:

def getAllValidPathsFrom(myMatrix): 
# def getDictRepresentationOf(myMatrix):
    dctOfMatrix = {}
    for row in range(len(myMatrix)):
        for column in range(len(myMatrix[row])):
            currPoint = (column, row)
            dctOfMatrix[currPoint] = myMatrix[row][column]

    lstIndicesOfAllMatrixPoints = list(dctOfMatrix.keys())
    setAllPossiblePaths = set()
    from itertools import permutations
    permutationsIndicesOfAllMatrixPoints = permutations(lstIndicesOfAllMatrixPoints)
    cutBranchAt = ()
    sizeOfCutBranch = 0
    for pathCandidate in permutationsIndicesOfAllMatrixPoints: 
        # print(pathCandidate, type(pathCandidate))
        if sizeOfCutBranch > 0:
            # print( "sizeOfCutBranch > 0", cutBranchAt )
            cutBranchAt = tuple(cutBranchAt)
            while cutBranchAt == pathCandidate[0:sizeOfCutBranch]:
                try:
                    pathCandidate = next(permutationsIndicesOfAllMatrixPoints)
                except:
                    break
        lstPossiblePath = []
        prevIndexTuple = pathCandidate[0]
        lstPossiblePath.append(prevIndexTuple)
        for currIndexTuple in pathCandidate[1:]:
            if (abs(currIndexTuple[0]-prevIndexTuple[0]) > 1) or (abs(currIndexTuple[1]-prevIndexTuple[1]) > 1) :
                sizeOfCutBranch = len(lstPossiblePath)+1
                cutBranchAt = tuple(lstPossiblePath+[currIndexTuple])
                break # current path indices not allowed in path (no jumps)
            else:
                if dctOfMatrix[currIndexTuple] in [ dctOfMatrix[index] for index in lstPossiblePath ] : 
                    sizeOfCutBranch = len(lstPossiblePath)+1
                    cutBranchAt = tuple(lstPossiblePath+[currIndexTuple])
                    break # only values different from all previous are allowed 
                else:
                    sizeOfCutBranch = 0
                    cutBranchAt = ()
                    lstPossiblePath.append(currIndexTuple)
                    prevIndexTuple = currIndexTuple
        if len(lstPossiblePath) > 1 and tuple(lstPossiblePath) not in setAllPossiblePaths: 
            setAllPossiblePaths.add(tuple(lstPossiblePath))

    return setAllPossiblePaths, dctOfMatrix
#:def getAllValidSkiingPathsFrom

theMatrix = [[3, 1, 3],
             [1, 1],
             [1, 2, 1, 3]]

lstAllPossiblePaths, dctOfMatrix = getAllValidPathsFrom(theMatrix)
setDifferentPossiblePaths = set(lstAllPossiblePaths)
setTpl = set()
for item in setDifferentPossiblePaths:
    lstTpl = []
    for element in item:
        lstTpl.append(dctOfMatrix[element])
    setTpl.add(tuple(lstTpl))
print(setTpl)

上面的代码在一个小矩阵上运行，因为大的矩阵会在计算上杀死它。由于小矩阵中值的特殊排列，因此可以在此证明，由于构建路径的限制性规则较多，因此不会生成所有排列。让我们比较变体1和答案变体2的输出：

The code above runs over a small matrix as the large one would kill it computationally. Because of special arrangement of values in the small matrix it is possible to demonstrate here that not all permutations are generated because of the more restrictive rules for building the path. Let's compare the outputs for the variant one and the variant two of the answer:

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

{(1, 2), (1, 3), (2, 1, 3), (3, 1), (2, 1), (3, 1, 2)}

因为在第二种变体中，路径必须经过相邻的矩阵元素，并不存在最长路径的所有排列，并且还包括较短的路径。

Because in the second variant the path has to go through adjacent matrix elements not all permutations of the longest path are there and there are also shorter paths included.

这篇关于Python列表中的特定路径组合或排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！