On 2011-11-11 14:44, lina wrote:
You are right, I did not think of this parts before. and actually the
initiative wish was to find possible paths, I mean, possible
substrings, all possible substrings. not the longest one, but at
least bigger than 3.
I had some time today and since you have changed your initial task (from
finding the longest common path to finding all common paths with a
minimum length) I've modified the code and came up with the following
solution:
def AllCommonPaths(list1, list2, minimum=3):
""" finds all common paths with a minimum length (default = 3)"""
# First we have to initialize the necessary variables:
# M is an empty table where we will store all found matches
# (regardless of their length)
M = [[0] * (len(list2)) for i in range(len(list1))]
# length is a dictionary where we store the length of each common
# path. The keys are the starting positions ot the paths in list1.
length = {}
# result will be a list of of all found paths
result =[]
# Now the hard work begins:
# Each element of list1 is compared to each element in list2
# (x is the index for list1, y is the index for list2).
# If we find a match, we store the distance to the starting point
# of the matching block. If we are in the left-most column (x == 0)
# or in the upper-most row (y == 0) we have to set the starting
# point ourself because we would get negative indexes if we look
# for the predecessor cell (M[x - 1][y - 1]). Else, we are one
# element farther away as the element before, so we add 1 to its
# value.
for x in range(len(list1)):
for y in range(len(list2)):
if list1[x] == list2[y]:
if (x == 0) or (y == 0):
M[x][y] = 1
else:
M[x][y] = M[x - 1][y - 1] + 1
# To get everything done in one pass, we update the length of
# the found path in our dictionary if it is longer than the minimum
# length. Thus we don't have to get through the whole table a
# second time to get all found paths with the minimum length (we
# don't know yet if we are already at the end of the matching
# block).
if M[x][y] >= minimum:
length[x + 1 - M[x][y]] = M[x][y]
# We now have for all matching blocks their starting
# position in list1 and their length. Now we cut out this parts
# and create our resulting list
for pos in length:
result.append(list1[pos:pos + length[pos]])
return result
I've tried to explain what I have done, but I'm sure you will still have
questions :-).
Is this close to what you want?
Bye, Andreas
PS: Here's the function again without comments:
def AllCommonPaths(list1, list2, minimum=3):
""" finds all common paths with a minimum length (default = 3)"""
M = [[0] * (len(list2)) for i in range(len(list1))]
length = {}
result =[]
for x in range(len(list1)):
for y in range(len(list2)):
if list1[x] == list2[y]:
if (x == 0) or (y == 0):
M[x][y] = 1
else:
M[x][y] = M[x - 1][y - 1] + 1
if M[x][y] >= minimum:
length[x + 1 - M[x][y]] = M[x][y]
for pos in length:
result.append(list1[pos:pos + length[pos]])
return result
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
