CODEWITHSUNDEEP
pythonpython-3.xrecursiontree
Fenil
Fenil

Reputation: 396

Passing modified list to each node of binary tree

I am writing a function to grow a tree:

def collect_append(collect,split):
 collect.append(split)
 return collect         


def tree(string,passwords,collect): #collect is a list and passwords is also a list

 matching_list = []
 match = 0
 if len(string)==0:
  print(collect)
  return 0
 for j in passwords:
   for i in range(min(len(j),len(string))):
     if string[i]!=j[i]:
      break
 else :
   matching_list.append(j)
   match = match + 1
 if match == 0:
  return 1
 else:
  for split in matching_list:
   x =tree(string.strip(split),passwords,collect_append(collect,split))
 return x

My question is, for each split in matching_list(say two), I want to add different strings to the existing list at that point (i.e. I want two versions of list).

In this case the collect_append function I use is modifying the list in first iteration of the for loop and using the same for further iterations. What I want is to just modify the collect list just for the parameter and without permanently changing it. Is there a way to do this?

Upvotes: 0

Views: 37

Answers (1)

cdlane
cdlane

Reputation: 41872

I see two serious errors in your code. First, this else clause is never executed:

for j in passwords:
    for i in range(...):
        if ...:
            break
else:
    ...

Since the break is in the inner for loop, the outer for loop is never exited via a break so the else is never taken. Second, this doesn't do what you want:

string.strip(split)

You're trying to remove split from the beginning of string but you're removing all the letters in split from both ends of string, bruising it badly. Here's one way to do it correctly:

string[len(split):]

I'm going to go out on a limb, and rewrite your code to do what I think you want it to do:

def tree(string, passwords, collect):

    length = len(string)

    if length == 0:
        return False

    matching_list = []

    for j in passwords:
        i = min(len(j), length)

        if string[:i] == j[:i]:
            matching_list.append(j)

    if not matching_list:
        return False

    result = False

    for split in matching_list:
        local_collection = list([split])
        if split == string or tree(string[len(split):], passwords, local_collection):
            collect.append(local_collection)
            result = True

    return result

collection = []

print(tree('dogcatcher', ['cat', 'catch', 'cher', 'dog', 'dogcat', 'dogcatcher', 'er'], collection))

print(collection)

OUTPUT

% python3 test.py
True
[['dog', ['cat', ['cher']], ['catch', ['er']]], ['dogcat', ['cher']], ['dogcatcher']]
%

Giving you a tree of all the ways to assemble string from the words in passwords.

Upvotes: 1

Related Questions