0

我仍然是 Python 的新手，所以请容忍我糟糕的语法和逻辑，如果有的话。无论如何，我有一个函数，我正试图干净地（请不要花哨的动作）打破递归循环。它是程序中的一个函数，它递归地遍历 1 和 0（参见下面的输入文件），并将相邻的 0 标识为不同的子集。我有一个名为“checkAllInOneDirection”的递归函数，它将遍历每个位置，向右、向左、向上、向下移动以检查 0。（对于每个递归，它在 4 个方向中的每一个上只剩下一个深度/更远）。

问题是由于某种原因，第三组的输出应该仅将 0,9 和 0,10 检测为一个不同的集合，但是当它在第二组检测后脱离递归时，它拾取 [0, 4] 和 [1 , 3] 在第三组检查的开始...有什么帮助吗？

这是输出 [行，列]：

Distinct subset found :  [[0, 0]]
Distinct subset found :  [[0, 3], [0, 4], [1, 3], [0, 5], [1, 4], [1, 5]]
Distinct subset found :  [[0, 9], [0, 4], [1, 3], [0, 10]]

正确的第三个子集应该只有：

Distinct subset found :  [[0, 9], [0, 10]]

这是一个示例输入文件：

01100011100100000
11100011111111011
10011111101011011

这是该函数的一个片段，它被称为“checkAllInOneDirection”：

isItLast = checkLast(forBoo, bakBoo, upBoo, dwnBoo)
if isItLast:
    for each in tempCatch:
        if not each in finalCatch:
            finalCatch.append(each)
    tempCatch=[]
    for each in newCatch:
        if not each in finalCatch:
            finalCatch.append(each)
    newCatch=[]
    return finalCatch, newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo
else:
    for each in tempCatch:
        if not each in finalCatch:
            finalCatch.append(each)
    tempCatch =[]
    for each in newCatch:    
        if not each in finalCatch:
            finalCatch.append(each)
            tempCatch.append(each)
    newCatch = []

return checkAllInOneDirection(finalCatch,tempCatch,recursiveCount,newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo)

这是整个功能，希望它只是澄清而不是让我的问题更加混乱：

def checkAllInOneDirection(finalCatch,tempCatch,recursiveCount,newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo):
    for each in range (0, len(tempCatch)):
        posToCheck = posToCheckBak = posToCheckUp = posToCheckDwn = [tempCatch[each][0], tempCatch[each][1]]
        newPosForward = checkForward(posToCheck, width)
        if newPosForward != False:
            tempLocale = locale[newPosForward[0]][newPosForward[1]]
        elif newPosForward == False:
            tempLocale = 1
        if newPosForward != False and tempLocale ==0 and not newPosForward in finalCatch and not newPosForward in newCatch:
            forVal = locale[newPosForward[0]][newPosForward[1]]
            newCatch.append(newPosForward)
            posToCheck = newPosForward
            forBoo = True
        elif newPosForward == False and tempLocale == 1 and not newPosForward in newCatch:
            forBoo = False

        newPosBackward = checkBackward(posToCheckBak)
        if newPosBackward != False:
            tempLocale = locale[newPosBackward[0]][newPosBackward[1]]
        elif newPosBackward == False:
            tempLocale = 1    
        if newPosBackward != False and tempLocale ==0 and not newPosBackward in finalCatch and not newPosBackward in newCatch:
            forVal = locale[newPosBackward[0]][newPosBackward[1]]
            newCatch.append(newPosBackward)
            posToCheckBak = newPosBackward
            bakBoo = True
        elif newPosBackward == False and tempLocale == 1 and not newPosBackward in newCatch:
            bakBoo = False

        newPosUp = checkUpRow(posToCheckUp)
        if newPosUp != False:
            tempLocale = locale[newPosUp[0]][newPosUp[1]]
        elif newPosUp == False:
            tempLocale = 1
        if newPosUp != False and tempLocale ==0 and not newPosUp in finalCatch and not newPosUp in newCatch:
            forVal = locale[newPosUp[0]][newPosUp[1]]
            newCatch.append(newPosUp)
            posToCheckUp = newPosUp
            upBoo = True
        elif newPosUp == False and tempLocale == 1 and not newPosUp in newCatch:
            upBoo = False

        newPosDwn = checkDwnRow(posToCheckDwn, height)
        if newPosDwn != False:
            tempLocale = locale[newPosDwn[0]][newPosDwn[1]]
        elif newPosDwn == False:
            tempLocale = 1
        if newPosDwn != False and tempLocale ==0 and not newPosDwn in finalCatch and not newPosDwn in newCatch:
            forVal = locale[newPosDwn[0]][newPosDwn[1]]
            newCatch.append(newPosDwn)
            posToCheckDwn = newPosDwn
            dwnBoo = True
        elif newPosDwn == False and tempLocale == 1 and not newPosDwn in newCatch:
            dwnBoo = False

    isItLast = checkLast(forBoo, bakBoo, upBoo, dwnBoo)
    if isItLast:
        for each in tempCatch:
            if not each in finalCatch:
                finalCatch.append(each)
        tempCatch=[]
        for each in newCatch:
            if not each in finalCatch:
                finalCatch.append(each)
        newCatch=[]
        return finalCatch, newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo
    else:
        for each in tempCatch:
            if not each in finalCatch:
                finalCatch.append(each)
        tempCatch =[]
        for each in newCatch:    
            if not each in finalCatch:
                finalCatch.append(each)
                tempCatch.append(each)
        newCatch = []

    return checkAllInOneDirection(finalCatch,tempCatch,recursiveCount,newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo)
4

3 回答 3

3

当使用递归时，你真的不应该使用像“loop”和“break”这样的短语。相反，将问题视为由在基本情况下变得微不足道的类似子问题组成。

您的一般问题是找到0与其他 's 相邻的0's 。（顺便说一下，这称为4 方向洪水填充。）所以较大的问题具有相同的子问题；所有已连接的列表与0以下组合相同：

  • 仅包含一个“起点”的列表0
  • 包含0“起点”右侧所有 ' 的列表0
  • 包含0“起点”左侧所有 ' 的列表0
  • 包含0“起点”上方所有 ' 的列表0
  • 包含0“起点”下方所有 ' 的列表0

所以在你的递归函数的某个地方，你会有一些效果：

return [[y,x]] + getConnectedZeros(x+1, y) + getConnectedZeros(x-1, y) + getConnectedZeros(x, y+1) + getConnectedZeros(x, y-1)

知道了这一点，您需要考虑您的基本案例，这些案例getConnectedZeros()必须返回与其子问题解决方案组合不同的东西。对我来说，基本情况是：

  • 当函数在包含1
  • 0当在已经“找到”的函数上调用函数时

对于这两种情况，只需返回一个空列表即可，因为何时[]返回，它代替了更多的递归调用。如果不包括这些条件，则递归将永远运行，并且永远不会休息打了一个基本案例。

基于这些想法，以下是您的问题的解决方案：

sampleInput = "01100011100100000\n11100011111111011\n10011111101011011"
inputMatrix = [[int(n) for n in row] for row in sampleInput.split('\n')] #matrix where each row is a list of the numbers from sampleInput

def getConnectedZeros(matrix, x, y, foundIndicies=[]):
    if 0<=y<len(matrix) and 0<=x<len(matrix[y]): #catch out of bounds
        if matrix[y][x] == 1: #catch 1s
            return []
        else:
            if not (x,y) in foundIndicies: #catch 0's we've already "seen"
                foundIndicies.append((x,y))
                return [[y,x]] + getConnectedZeros(matrix, x+1, y, foundIndicies) + getConnectedZeros(matrix, x-1, y, foundIndicies) + getConnectedZeros(matrix, x, y+1, foundIndicies) + getConnectedZeros(matrix, x, y-1, foundIndicies)
            else:
                return []
    else:
        return []


#Now we can just loop through the inputMatrix and find all of the subsets
foundZeroIndicies = []
subsets = []
y = -1
for row in inputMatrix:
    y += 1
    x = -1
    for val in row:
        x += 1
        if (not [y,x] in foundZeroIndicies) and val==0:
            zerosList = getConnectedZeros(inputMatrix, x, y)
            subsets.append(zerosList)
            foundZeroIndicies.extend(zerosList)
for subset in subsets:
    print "Distinct Subset Found  : ", subset

希望这会有所帮助。（希望它是连贯的，现在是凌晨 5 点......）

于 2012-08-30T08:55:45.360 回答
2

我的代码是使用递归函数 walk() 的示例。我希望它能帮助你解决问题。

input = ['01100011100100000',
         '11100011111111011',
         '10011111101011011']
col_len = 17
row_len = 3

walked = []
output = []

def walk(subset_in, row, col):
    if (0 <= row < row_len) and (0 <= col < col_len) and (row, col) not in walked:
        walked.append((row, col))
        if input[row][col] == '0':
            if subset_in is not None:
                subset = subset_in
            else:
                subset = []

            subset.append((row, col))
            walk(subset, row, col+1)
            walk(subset, row+1, col)
            walk(subset, row, col-1)
            walk(subset, row-1, col)

            if subset_in is None:
                output.append(subset)

for row in xrange(row_len):
    for col in xrange(col_len):
        if (row, col) not in walked:
            walk(None, row, col)

for subset in output: print subset
于 2012-08-30T08:48:38.743 回答
1

要摆脱递归，您需要使用 return。如果您的递归进一步继续，您需要重新考虑您的基本情况。

只是为了好玩，我尝试为此使用 networkx，而不是它回答了您的问题：

data = """01100011100100000
11100011111111011
10011111101011011""".splitlines()

import networkx

G = networkx.Graph()
found = set()

for i, row in enumerate(data):
    for j, c in enumerate(row):
        if c == '0':
            found.add((i, j))
            if i + 1 < len(data) and data[i + 1][j] == '0':
                G.add_edge((i, j), (i + 1, j))
            if j + 1 < len(row) and row[j + 1] == '0':
                G.add_edge((i, j), (i, j + 1))

groups = map(list, networkx.connected_component_subgraphs(G))
group_nodes = set(node for group in groups for node in group)
individuals = found - group_nodes

print groups
print individuals

"""
[[(0, 15), (0, 14), (1, 14), (0, 13), (0, 12), (0, 16), (2, 14)], [(1, 3), (1, 4), (1, 5), (0, 5), (0, 4), (0, 3)], [(2, 1), (2, 2)], [(0, 9), (0, 10)]]
set([(0, 0), (2, 11), (2, 9)])
"""
于 2012-08-30T07:44:06.613 回答