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