|
|
A109382
|
|
Levenshtein distance between successive English names of nonnegative integers, excluding spaces and hyphens.
|
|
3
|
|
|
4, 3, 4, 5, 3, 3, 4, 5, 4, 3, 4, 4, 6, 3, 3, 2, 4, 4, 3, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 6, 3, 3, 4, 5, 3, 3, 4, 5, 4, 6, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 8, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3, 4, 5, 4, 7, 3, 3, 4, 5, 3, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
LINKS
|
|
|
FORMULA
|
a(n) = LD(nameof(n), nameof(n+1)).
|
|
EXAMPLE
|
a(0) = 4 since LD(ZERO,ONE) requires 4 edits.
a(1) = 3 since LD(ONE,TWO) which requires 3 substitutions.
a(2) = 4 since LD(TWO,THREE) = requires 4 edits (leave the leftmost T unchanged), then 2 substitutions (W to H, O to R), then 2 insertions (E,E).
a(4) = 3 as LD(FOUR,FIVE) leaves the leftmost F unchanged, then requires 3 substitutions. From FIVE to SIX leaves the I unchanged. From SIX to SEVEN leaves the S unchanged. From TEN to ELEVEN leaves the EN unchanged. From ELEVEN to TWELVE leaves an E,L,V,E unchanged. From THIRTEEN to FOURTEEN leaves RTEEN unchanged. TWENTYNINE to THIRTY takes 7 edits. THIRTYNINE to FORTY takes 7 edits. SEVENTYNINE to EIGHTY takes 8 edits. EIGHTYNINE to NINETY takes 7 edits. NINETYNINE to ONEHUNDRED takes 7 edits.
|
|
MAPLE
|
with(StringTools):
seq(Levenshtein(Select(IsAlpha, convert(n, english)), Select(IsAlpha, convert(n+1, english))), n=0..200); # Robert Israel, Jan 23 2018
|
|
MATHEMATICA
|
(* First copy b109382.txt out of A109382 then *) 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[x_] := Block[{str = ToString@ lst[[x]], len}, len = StringLength@ str; StringInsert[str, ", ", Range[2, len]]]
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,word
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|