Python: Logischer Fehler in Rekursion unter Doppel for-Schleife

Question

BackGround

ich an einem Projekt arbeite, wo ich eine Reihe von Zeichenfolgen zu vergleichen und nur diejenigen zu halten, die unique oder distinct sind. Uniq oder distinct bedeutet, dass keine zwei Strings sein sollten,
A) Palindrome, z.B. ABA' , 'BCB'
B) Reverse of each other. e.g. ‚ABCD‘ and ' DCBA ‚ C) Same as each other, e.g.‚ABC‘and‘ ABC'`

Wenn die Liste solche Attribute nicht enthält, dann nur Programm sollte einer von ihnen halten und andere entfernen.

Für z.B. Ich bin mit itertools und permutations und combination Module wie unten eine Liste zu erzeugen,
aList= ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA', 'ABC']

Und es durch zwei for-Schleifen verarbeiten.
Outer for loop verarbeitet jede Nummer von Anfang bis Ende, bis End of List -1 item getroffen wird.
Inner for Schleife Prozesse von start + 1 Artikel zu End of List. Auf diese Weise vergleichen die beiden Schleifen immer zwei verschiedene Strings.

Nun ist es notwendig, diese Logik mitRecursions zu erhalten.

Was

Works Ich habe folgendes Programm schreiben, das jedes Mal der Attribute gefunden und die doppelten Elemente werden entfernt in Rekursion Funktion aufruft.

Was nicht

Die Rekursion funktioniert nur funktioniert, wenn mindestens ein Element in der Liste ist es, die Attribute Kriterien erfüllt ist und gelöscht. Wenn die saveFound = True. Ich benutzte eine andere Variable, um Teilfunde mit found = True auch zu verfolgen, aber muss es nicht wirklich machen, damit es funktioniert.

Das Programm schlägt fehl, wenn für ein bestimmtes Element kein passendes Attribut in der Liste vorhanden ist. Wir sind jedoch erst fertig, wenn alle Elemente überprüft wurden und wir zwei Elemente in der Liste haben. Dann gehen wir.

Was ich brauche Hilfe mit

Ich habe zusätzliche print-Anweisungen setzen (in #DEBUG Endung) zu sehen, welche Artikel ersetzt. Ich muss wissen, wie die rekursive Funktion im Programm verwendet werden kann, um die Situation zu beheben, wo es keine Duplikate in Bezug auf das erste Element gibt. Das Programm führt einen Selbstvergleich durch und entfernt sich selbst von der Liste. Sieht aus, als ob es für diese Situation keine äußere for-Schleife erreicht. Jede Eingabe/Korrektur wird geschätzt.

Programm:

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

OK, also habe ich versucht, den Code zu bekommen, während Wechsel so wenig wie möglich zu arbeiten. Fazit ist, ich glaube nicht, dass Sie ohne Änderung Ihrer aList entkommen können, da Sie Ihren Status in jedem rekursiven Schritt irgendwie verfolgen müssen.

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 

Ich habe Kommentare hinzugefügt, damit Sie verstehen, was ich für jeden Schritt mache. Lassen Sie mich wissen, wenn dies nicht Ihren Anforderungen entspricht!