editing

approved

The Levenshtein distance (also called edit distance) between two strings is equal to the minimum number of insertion, deletion, or substitution operations needed to transform one string into the other. It is named after the Russian scientist Vladimir Levenshtein, who developed this metric in 1965. Levenshtein distance is a generalization of Hamming distance.

approved

editing

Joerg Arndt: Plagiarism.

_Robert G. Wilson v (rgwv(AT)rgwv.com), _, Jan 26 2006

OEIS Server: https://oeis.org/edit/global/156

Michael Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a> [It has been suggested that this algorithm gives incorrect results sometimes. - . - _N. J. A. Sloane (njas(AT)research.att.com)]_]

OEIS Server: https://oeis.org/edit/global/110

Michael Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a> [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane (njas](AT)research.att.com)]

base,nonn,new

Levenshtein distance between n considered as a decimal string and n considered as a binary string.

0, 2, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 4, 4, 5, 5, 5, 5

1,2

a(n) = minimal number of editing steps (delete, insert or substitute) to transform n_10 into n_2.

The Levenshtein distance (also called edit distance) between two strings is equal to the minimum number of insertion, deletion, or substitution operations needed to transform one string into the other. It is named after the Russian scientist Vladimir Levenshtein, who developed this metric in 1965. Levenshtein distance is a generalization of Hamming distance.

Michael Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a> [It has been suggested that this algorithm gives incorrect results sometimes. - njas]

levenshtein[s_List, t_List] := Module[{d, n = Length@s, m = Length@t}, Which[s === t, 0, n == 0, m, m == 0, n, s != t, d = Table[0, {m + 1}, {n + 1}]; d[[1, Range[n + 1]]] = Range[0, n]; d[[Range[m + 1], 1]] = Range[0, m]; Do[d[[j + 1, i + 1]] = Min[d[[j, i + 1]] + 1, d[[j + 1, i]] + 1, d[[j, i]] + If[s[[i]] === t[[j]], 0, 1]], {j, m}, {i, n}]; d[[ -1, -1]]]];

f[n_] := levenshtein[ IntegerDigits[n], IntegerDigits[n, 2]]; Array[f, 105]

Cf. A000027, A007088, first occurrence: A115778.

base,nonn

Robert G. Wilson v (rgwv(AT)rgwv.com), Jan 26 2006

approved