cp's OEIS Frontend

A248327 Levenshtein distance of n and its reversal in decimal representation, cf. A004086.

%I A248327 #4 Oct 05 2014 02:16:46
%S A248327 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,
%T A248327 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,
%U A248327 2,2,1,2,2,2,2,2,2,0,2,2,1,2,2,2,2,2
%N A248327 Levenshtein distance of n and its reversal in decimal representation, cf. A004086.
%C A248327  a(n) = number of editing steps (replace, delete and insert) to transform n to A004086(n);
%C A248327 a(A002113(n)) = 0, a(10*A002113(n)) = 1 for n > 0;
%C A248327 a(A248336(n)) = n and a(m) != n for m < A248336(n).
%H A248327 Reinhard Zumkeller, <a href="/A248327/b248327.txt">Table of n, a(n) for n = 0..10000</a>
%H A248327 Haskell Wiki, <a href="http://www.haskell.org/haskellwiki/Edit_distance">Edit distance</a>
%H A248327 WikiBooks: Algorithm Implementation, <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance">Levenshtein distance</a>
%H A248327 Wikipedia, <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein distance</a>
%o A248327 (Haskell)
%o A248327 a248327 0 = 0
%o A248327 a248327 n = levenshtein (show n) (dropWhile (== '0') $ reverse $ show n)
%o A248327 levenshtein :: (Eq t) => [t] -> [t] -> Int
%o A248327 levenshtein us vs = last $ foldl transform [0..length us] vs where
%o A248327    transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
%o A248327       compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
%Y A248327 Cf. A004086, A002113, A248336.
%K A248327 nonn,base
%O A248327 0,13
%A A248327 _Reinhard Zumkeller_, Oct 05 2014