A248327 Levenshtein distance of n and its reversal in decimal representation, cf. A004086.
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 0, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 0, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 0, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 0, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 0, 2, 2, 1, 2, 2, 2, 2, 2
Offset: 0
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
- Haskell Wiki, Edit distance
- WikiBooks: Algorithm Implementation, Levenshtein distance
- Wikipedia, Levenshtein distance
Programs
-
Haskell
a248327 0 = 0 a248327 n = levenshtein (show n) (dropWhile (== '0') $ reverse $ show n) levenshtein :: (Eq t) => [t] -> [t] -> Int levenshtein us vs = last $ foldl transform [0..length us] vs where transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
Comments