Take the 2-minute tour ×

I implemented an n-dimensional longest common subsequence in python, but it's buggy in 3d.

# -*- coding: utf-8 -*-
from collections import defaultdict
from operator import itemgetter

def count(limits):
    idcs = [0] * len(limits)
    while True:
        yield tuple(idcs)
        for n in range(len(limits)-1, -1, -1):
            idcs[n] += 1
            if idcs[n] != limits[n]:
            elif n == 0:
                raise StopIteration
                idcs[n] = 0

def make_grid(words):
    size = len(words)
    default_backpointer = tuple([-1]*size)
    grid = defaultdict(lambda: (0, default_backpointer))
    for indices in count([len(word) for word in words]):
        chars = {L[ind] for L, ind in zip(words, indices)}
        if len(chars) == 1:
            backpointer = tuple([coord - 1 for coord in indices])
            grid[indices] = (grid[backpointer][0] + 1, backpointer, chars.pop())
            iter = count([2]*size)
            iter.next() # To avoid self-reference
            values = []
            for previous in iter:
                backpointer = tuple([indices[index] - previous[index] for index in xrange(size)])
                values.append((grid[backpointer][0], backpointer, None))
            grid[indices] = max(values, key=itemgetter(0))
    return grid

def lcs(*words):
    grid = make_grid(words)
    best = []
    position = tuple([len(word) - 1 for word in words])

    while -1 not in position:
        pointer = grid[position]
        position = pointer[1]

    best = [item for item in best if item is not None ]
    return best

#print(lcs("HUMAN", "CHIMPANZEE", "WOMAN"))
print(lcs("MAN", "MAFN", "FMAN"))

Output: ['N']

share|improve this question
Code Review is strictly for working code. Please feel free to bring it back when it is working for further improvement. –  Winston Ewert Dec 11 '11 at 18:38
add comment

migrated from codereview.stackexchange.com Dec 11 '11 at 18:38

This question came from our site for peer programmer code reviews.

1 Answer

up vote 0 down vote accepted

Found the bug. itemgetter(0) for the max function, therefore wrong backpointers.

share|improve this answer
add comment

Your Answer


