Entry

List changes algorithm [see snippet for explanation ;-]

Jul 5th, 2000 10:01
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 200, Moshe Zadka

"""
Packages: basic_datatypes.lists;maths
"""
# The standard algorithm for determining the shortest
# number of add/delete/change operations which can bring
# us from one list to another in a short, a bit optimized
# and (hopefully) clear algorithm.
# By (also) recording the choices we do each step, 
# we could have a truly "diff-compatible" algorithm.
# Cheers!
def distance(a,b):
        n, m = map(len, (a,b))
        if n>m:  # Make sure n<=m
                (a, n), (b, m) = (b, m), (a, n)
        range_m, range_n = map(range, (m, n))
        current = range(0, n+1)
        for i in range_m:
                previous, current = current, [i+1]
                for j in range_n:
                        add, delete = previous[j+1]+1, current[j]+1
                        change = previous[j] + (a[j]!=b[i])
                        current.append(min(add, delete, change))
        return current[n]
# small test, added by PSST
l1 = range(10)
l2 = [1,5,7,12,3,8,8]
print distance(l1,l2)