Python：double for循环下递归逻辑错误

Question

背景

我正在做一个项目，我需要比较一组字符串并只保留 unique 或 distinct 的字符串。 Uniq 或 distinct 表示不应有两个字符串，
A）回文，例如ABA' , 'BCB'<br> B) 彼此相反。例如'ABCD'and 'DCBA'C) Same as each other, e.g.'ABC'and'ABC'`

如果列表确实包含这样的属性，那么程序应该只保留其中一个并删除其他。

例如我正在使用 itertools 和 permutations 以及 combination 模块来生成如下列表，
aList= ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA', 'ABC']

并通过两个 for 循环处理它。
外部 for 循环从头到尾处理每个数字，直到 End of List -1 项被命中。
内部 for 循环处理从 start + 1 项到 End of List。这样两个循环总是比较两个不同的字符串。

现在，需要使用 Recursions.

来完成这个逻辑

有效方法

我确实编写了以下程序，每次找到属性并删除重复项时都会调用递归函数。

什么不起作用

递归仅在列表中至少有一项与属性条件匹配并被删除时才有效。当saveFound = True。我也使用另一个变量来跟踪使用 found = True 的部分发现，但还没有完全让它工作。

当特定项目的列表中没有匹配属性时，程序失败。但是，直到检查完所有项目并且我们只剩下列表中的最后两个项目时，我们才算完成。然后我们退出。

我需要什么帮助

我添加了额外的打印语句（以#debug 结尾）以查看正在替换的项目。我需要知道如何在程序中使用递归函数来解决第一项没有重复项的情况。该程序正在进行自我比较并将其自身从列表中删除。对于这种情况，它似乎没有到达外部 for 循环。感谢任何输入/修复。

程序:

from itertools import combinations, permutations

""" Process list to generate Unique strings matching given criteria """
def uniqLst(aList):

    """ Iterate through outer loop to compare each string until End of Loop """
    firstItem = 0
    lastItem = len(aList) -1
    for item1 in aList[firstItem:lastItem:]:

        saveFound = False
        print "Starting Next for Loop : Loop Length", len(aList) #Debug Data
        print "input List=", aList #Debug Data

        for item2 in aList[firstItem + 1:lastItem + 1:]:
            #Compare first item with next
            print "Comparing item1, item2 =", item1 , item2 #Debug Data

            """ Check if second string is reverse / palindrome or same """      
            if  item1[::-1] == item2 or item1 == item2:
                found = True
                saveFound = True
                print "Removing", item2 #Debug Data
                aList.remove(item2) # Remove second item matching criteria
            else:
                found = False

        """One iteration cycle is complete"""
        if saveFound == True:
            print "Starting Next Iteration" #Debug Data
            uniqLst(aList)              #Force load of new aList

    #External loop is complete exit Function
    return aList


""" Main Function """    
if __name__== "__main__":

    tmpLst1 = ["".join(x) for x in permutations('ABC', 3)]
    tmpLst2 = ["".join(x) for x in combinations('ABC', 3)]

    checkStrLst = tmpLst1 + tmpLst2

    finalList =  uniqLst(checkStrLst)
    print "========================"
    print "finalList", finalList

OutPut

Python 2.7.9 (default, Dec 10 2014, 12:24:55) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
Starting Next for Loop : Loop Length 7
input List= ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA', 'ABC']
Comparing item1, item2 = ABC ACB
Comparing item1, item2 = ABC BAC
Comparing item1, item2 = ABC BCA
Comparing item1, item2 = ABC CAB
Comparing item1, item2 = ABC CBA
Removing CBA
Comparing item1, item2 = ABC ABC
Removing ABC
Starting Next Iteration
Starting Next for Loop : Loop Length 5
input List= ['ACB', 'BAC', 'BCA', 'CAB', 'ABC']
Comparing item1, item2 = ACB BAC
Comparing item1, item2 = ACB BCA
Removing BCA
Comparing item1, item2 = ACB CAB
Comparing item1, item2 = ACB ABC
Starting Next Iteration
Starting Next for Loop : Loop Length 4
input List= ['ACB', 'BAC', 'CAB', 'ABC']
Comparing item1, item2 = ACB BAC
Comparing item1, item2 = ACB CAB
Comparing item1, item2 = ACB ABC
Starting Next for Loop : Loop Length 4
input List= ['ACB', 'BAC', 'CAB', 'ABC']
Comparing item1, item2 = BAC BAC
Removing BAC
Comparing item1, item2 = BAC CAB
Removing CAB
Comparing item1, item2 = BAC ABC
Starting Next Iteration
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = ACB ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = CAB ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = BAC ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = BCA ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = CAB ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = ACB ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = BAC ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = BCA ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = CAB ABC
Starting Next for Loop : Loop Length 2
input List= ['ACB', 'ABC']
Comparing item1, item2 = CBA ABC
Removing ABC
Starting Next Iteration
========================
finalList ['ACB']
>>>

Answer 1

好的，所以我尝试让您的代码在尽可能少的更改下工作。底线是，我不认为你可以在不更改 aList 的情况下逃脱，因为你必须以某种方式在每个递归步骤中跟踪你的状态。

from itertools import combinations, permutations

""" Process list to generate Unique strings matching given criteria """
def uniqLst(aList, finalList):

    """ Iterate through outer loop to compare each string until End of Loop """

    # Terminate if length is 0
    if(len(aList) == 0):
        return

    # Initialize local values
    found = False
    item1 = aList[0];

    # Go through list and compare with first item
    for item2 in aList[1:len(aList)]:

        """ Check if second string is reverse / palindrome or same """
        if item1[::-1] == item2 or item1 == item2:
            found = True
            print "Removing", item2 #Debug Data
            aList.remove(item2) # Remove second item matching criteria

    # If no item matches, add first item to final list
    if found != True:
        temp = aList.pop(0)
        finalList.append(temp)

        # Recursively call this function with updated aList
    uniqLst(aList, finalList)

    return


""" Main Function """
if __name__== "__main__":

    tmpLst1 = ["".join(x) for x in permutations('ABC', 3)]
    tmpLst2 = ["".join(x) for x in combinations('ABC', 3)]

    checkStrLst = tmpLst1 + tmpLst2

    finalList = []
    uniqLst(checkStrLst, finalList)
    print "========================"
    print "finalList", finalList

我添加了评论以帮助您了解我在每个步骤中所做的工作。如果这不符合您的要求，请告诉我！

Python：double for循环下递归逻辑错误

Python: Logical error in recursion under double for loop

python

recursion

for-loop

list

itertools