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]:
break
elif n == 0:
raise StopIteration
else:
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]):
print(indices)
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())
else:
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))
print(grid.keys())
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]
best.append(pointer[2])
position = pointer[1]
best = [item for item in best if item is not None ]
best.reverse()
return best
#print(lcs("HUMAN", "CHIMPANZEE", "WOMAN"))
print(lcs("MAN", "MAFN", "FMAN"))
Output: ['N']
