0

私はまだPythonの初心者なので、構文とロジックが悪い場合は許容してください。とにかく、再帰ループから抜け出そうとしている関数があります（派手な動きはしないでください）。これは、1と0を再帰的に繰り返し（以下の入力ファイルを参照）、隣接する0を個別のサブセットとして識別するプログラムの関数です。「checkAllInOneDirection」と呼ばれる再帰関数があり、各位置をループして、右、左、上、下の位置に移動して0をチェックします。（再帰ごとに4つの方向のそれぞれで左に1つだけ深く/さらに進みます）。

問題は、何らかの理由で、3番目のセットの出力が1つの別個のセットとして0,9と0,10のみを検出するはずですが、2番目のセットの検出後に再帰から抜け出すと、[0、4]と[1 、3] 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]]

正しい3番目のサブセットは次のようになります。

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、他の'の隣にある'を見つけること0です。（ちなみに、これは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 に答える