|
%I #30 Dec 01 2018 07:59:43
%S 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,
%T 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,
%U 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
%N Levenshtein distance between successive English names of nonnegative integers, excluding spaces and hyphens.
%H Robert Israel, <a href="/A109382/b109382.txt">Table of n, a(n) for n = 0..10000</a>
%H Michael Gilleland, <a href="https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance, in Three Flavors</a>.
%H V. I. Levenshtein, <a href="https://doi.org/10.1006/jcta.2000.3081">Efficient reconstruction of sequences from their subsequences or supersequences</a>, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.
%H Landon Curt Noll, <a href="http://www.isthe.com/chongo/tech/math/number/number.html">The English Name of a Number</a>.
%H Robert G. Wilson v, <a href="https://oeis.org/a001477/a001477.txt">American English names for the numbers from 0 to 100999 without spaces or hyphens</a>.
%F a(n) = LD(nameof(n), nameof(n+1)).
%e a(0) = 4 since LD(ZERO,ONE) requires 4 edits.
%e a(1) = 3 since LD(ONE,TWO) which requires 3 substitutions.
%e 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).
%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.
%p with(StringTools):
%p seq(Levenshtein(Select(IsAlpha, convert(n,english)),Select(IsAlpha,convert(n+1,english))),n=0..200); # _Robert Israel_, Jan 23 2018
%t (* 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]]]
%Y Cf. A001477, A005589, A081355, A081356, A081230, A109809, A109811.
%K easy,nonn,word
%O 0,1
%A _Jonathan Vos Post_, Aug 25 2005
%E More terms from _Robert G. Wilson v_, Jan 31 2006
%E Corrected by _Robert Israel_, Jan 23 2018
|
