3
$\begingroup$

I'd like the most efficient Mathematica code for making a formal tree graph whose nodes are valid English word strings (in DictionaryLookup[ ]) and directed links represent the relation 'insertion of a single letter anywhere in the source string word.' The tree graph should be organized with the one-letter word 'a' at the center, then all the two-letter words (e.g., 'ad', 'ah', 'am', 'an', 'as', 'at', 'ax', 'fa', 'ha', 'la', 'ma', 'pa', 'ta', 'ya') should be arranged around the center, at radius = 1. Then at radius = 2 are all the three-letter English words (e.g., 'ask', 'ant', etc.) linked from their source words at radius = 1; for instance, there will be a link from 'as' to 'ask', since one can obtain 'ask' by insertion of 'k' in the final slot after 'as'. And so on, up to the maximum number of such letters (which I believe is 8, at radius = 7).

The only other one-letter English word is 'i' (actually 'I'), which would generate its own directed tree graph.

Repeat for different languages (e.g., French, Italian, Spanish, ...).

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ That sounds awfully close to a homework I recently gave to my students :) $\endgroup$
    – Dr. belisarius
    Oct 13 '14 at 21:55
  • 4
    $\begingroup$ Please allow me to suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$
    – Dr. belisarius
    Oct 13 '14 at 21:58
  • $\begingroup$ I doubt anybody will want to answer this if its really a homework for @belisarius' course. Probably if the OP showed some work of his own, and divided the problem into smaller tasks... probably. $\endgroup$
    – rhermans
    Oct 14 '14 at 7:04
  • 2
    $\begingroup$ @rhermans Oh, I can't know for certain, the concept matches but the text doesn't. In any case that shouldn't refrain anyone from answering. A rant follows: Although I prefer HW questions being addressed in other ways, I don't forbid asking for help and then using it ethically (ie showing what they got as external help and what is their "original" effort). Also, my students are aware that I monitor a few sites because I'm very interested in learning new ways to achieve the HW goals. $\endgroup$
    – Dr. belisarius
    Oct 14 '14 at 10:13
4
$\begingroup$ 
ClearAll[dL];
dL = Function[{str},
   With[{s = Last@str}, Thread[s -> DictionaryLookup[Alternatives @@
        (StringExpression @@              
            StringSplit[StringInsert[s, ".", #], 
             "." -> LetterCharacter] & /@
          Range[1 + StringLength@s])]]], Listable];

edges = DeleteDuplicates@Flatten@Rest@NestList[dL, {"a" -> "a"}, 7];


style = {GraphLayout -> {"RadialEmbedding", "RootVertex" -> "a"}, 
   VertexStyle -> {_ :> White, 
                 (x_ /; StringLength[x] == 8) -> Directive[{Red, PointSize[.01]}], 
                  "a" -> Directive[{Blue, PointSize[.01]}]}, 
   VertexLabels -> {Placed["Name", Tooltip], 
       (x_ /; StringLength[x] == 8) -> Placed[Style[x, Red, 12], {Tooltip, Before}]}, 
   VertexShapeFunction -> "Point", LabelStyle -> Red,ImageSize -> 700,
   EdgeStyle -> Directive[Opacity[.5], Hue[.15, .5, .8]], 
   Background -> Black, EdgeShapeFunction -> (Line[#1] &) };

gg = Graph[edges, style];
{VertexCount[gg], EdgeCount[gg]}
(*  {2511, 3828} *)

gg

enter image description here

Select[VertexList[gg], StringLength[#] == 8 &]

{"blasters", "blathers", "boasters", "brandied", "brattier", "chanters", "chastens", 
 "chatters", "chattier", "cheaters", "clatters", "cleansed", "cleanser", "cleanses",
  "cleavers", "coasters", "crankier", "cremated", "cremates", "drafters", "draftier",
  "flatters", "flattery", "gamblers", "gestated", "gestates", "grafters", "grafting",
  "grandeur", "granters", "granting", "gratings", "gyrating", "heathers", "heathery",
  "Jeannine", "leathers", "leathery", "loathers", "managers", "martinis", "masterly",
  "maximals", "palpated", "palpates", "pastiest", "pastimes", "pastries", "patterns",
  "planners", "planters", "platters", "prattled", "prattler", "prelates", "rattlers",
  "rattlier", "reflated", "reflates", "relapsed", "relapses", "relaters", "restated", 
  "restates", "roadster", "roasters", "scantier", "scantily", "shatters", "sheathed",
  "sheathes", "slammers", "slathers", "sparkled", "sparsest", "spatters", "splatted",
  "splatter", "stampede", "stampers", "staplers", "starkers", "starters", "startled",
  "statures", "statuses", "statutes", "strapped", "streamed", "swaddled", "swatches",
  "testates", "theaters", "threader", "trampers", "trampled", "trampler", "trappers",
  "twaddled"}

Continuing beyond 7 steps:

laststep =DeleteDuplicates[Last /@ Flatten[dL /@ 
                          Thread[1 -> Select[VertexList[gg], StringLength[#] == 8 &]]]

{"cleansers", "splatters", "prattlers", "restarted", "roadsters","stampeded", "stampedes", 
"threaders", "threadier", "tramplers"}

DeleteDuplicates[Last /@ Flatten[dL /@ Thread[1 -> laststep]]]
(* {} *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ The question is purely academic. I feel somehow sorry for all your overwritings +1 :) $\endgroup$
    – eldo
    Oct 15 '14 at 20:58
  • $\begingroup$ @kguler beautiful layout...instructive+1 :) $\endgroup$
    – ubpdqn
    Oct 16 '14 at 1:49
  • $\begingroup$ The initial question stemmed from a problem posted in MIT Technology Review. This final answer is excellent and the layout clear. One teeny improvement would be to allow the user to mouseover a node and have the path from the root ("a") to that selected node become highlighted and each node on the path displayed its word. But such refinements are not needed. $\endgroup$
    – David G. Stork
    Oct 16 '14 at 21:35
5
$\begingroup$

I post this (if I understand the question from title and text: single letter addition anywhere in string) to illustrate how unwieldy the graph gets just 3 levels deep. Here just starting with "a".

fun[x_] := With[{c = Characters[x]},
  Thread[x ->
    Select[
     DictionaryLookup[
      StringExpression @@ Riffle[c, ___, {1, 2 Length@c + 1, 2}]], 
     StringLength@# == StringLength@x + 1 &]]]

Building graph from "a", just for 3 iterations:

gr = NestList[Join @@ fun /@Union[ #[[All, 2]]] &, fun["a"], 3];

Visualizing:

Graph[Join @@ gr]

enter image description here

This would be unwieldy to label/interpret without much cleverer ways to cone down on or render interactive (I look forward to approaches):

The edges for just 2 interations(!):

{"a" -> "ad", "a" -> "ah", "a" -> "am", "a" -> "an", "a" -> "as", 
 "a" -> "at", "a" -> "ax", "a" -> "fa", "a" -> "ha", "a" -> "la", 
 "a" -> "ma", "a" -> "pa", "a" -> "ta", "a" -> "ya", "ad" -> "add", 
 "ad" -> "ado", "ad" -> "ads", "ad" -> "adz", "ad" -> "aid", 
 "ad" -> "and", "ad" -> "bad", "ad" -> "cad", "ad" -> "dad", 
 "ad" -> "fad", "ad" -> "gad", "ad" -> "had", "ad" -> "lad", 
 "ad" -> "mad", "ad" -> "pad", "ad" -> "sad", "ad" -> "tad", 
 "ad" -> "Tad", "ad" -> "wad", "ah" -> "aah", "ah" -> "aha", 
 "ah" -> "ash", "ah" -> "bah", "ah" -> "nah", "ah" -> "pah", 
 "ah" -> "rah", "am" -> "aim", "am" -> "amp", "am" -> "arm", 
 "am" -> "cam", "am" -> "Cam", "am" -> "dam", "am" -> "ham", 
 "am" -> "Ham", "am" -> "jam", "am" -> "lam", "am" -> "mam", 
 "am" -> "Nam", "am" -> "Pam", "am" -> "ram", "am" -> "Sam", 
 "am" -> "tam", "am" -> "yam", "an" -> "and", "an" -> "ans", 
 "an" -> "ant", "an" -> "any", "an" -> "awn", "an" -> "ban", 
 "an" -> "can", "an" -> "Dan", "an" -> "fan", "an" -> "Han", 
 "an" -> "Ian", "an" -> "Jan", "an" -> "Kan", "an" -> "man", 
 "an" -> "Man", "an" -> "nan", "an" -> "Nan", "an" -> "pan", 
 "an" -> "Pan", "an" -> "ran", "an" -> "San", "an" -> "tan", 
 "an" -> "van", "an" -> "Van", "an" -> "wan", "as" -> "abs", 
 "as" -> "ads", "as" -> "ans", "as" -> "ash", "as" -> "ask", 
 "as" -> "asp", "as" -> "ass", "as" -> "gas", "as" -> "has", 
 "as" -> "mas", "as" -> "pas", "as" -> "was", "at" -> "act", 
 "at" -> "aft", "at" -> "ant", "at" -> "apt", "at" -> "art", 
 "at" -> "ate", "at" -> "bat", "at" -> "cat", "at" -> "eat", 
 "at" -> "fat", "at" -> "hat", "at" -> "mat", "at" -> "Nat", 
 "at" -> "oat", "at" -> "pat", "at" -> "Pat", "at" -> "rat", 
 "at" -> "sat", "at" -> "tat", "at" -> "vat", "ax" -> "axe", 
 "ax" -> "fax", "ax" -> "lax", "ax" -> "Max", "ax" -> "sax", 
 "ax" -> "Sax", "ax" -> "tax", "ax" -> "wax", "fa" -> "fab", 
 "fa" -> "fad", "fa" -> "fag", "fa" -> "fan", "fa" -> "far", 
 "fa" -> "fat", "fa" -> "fax", "fa" -> "fay", "fa" -> "Ufa", 
 "ha" -> "aha", "ha" -> "had", "ha" -> "hag", "ha" -> "haj", 
 "ha" -> "ham", "ha" -> "hap", "ha" -> "has", "ha" -> "hat", 
 "ha" -> "haw", "ha" -> "hay", "la" -> "Ila", "la" -> "lab", 
 "la" -> "lac", "la" -> "lad", "la" -> "lag", "la" -> "lam", 
 "la" -> "lap", "la" -> "lav", "la" -> "law", "la" -> "lax", 
 "la" -> "lay", "la" -> "lea", "la" -> "Ola", "ma" -> "mac", 
 "ma" -> "mad", "ma" -> "mam", "ma" -> "man", "ma" -> "map", 
 "ma" -> "mar", "ma" -> "mas", "ma" -> "mat", "ma" -> "maw", 
 "ma" -> "may", "pa" -> "pad", "pa" -> "pah", "pa" -> "pal", 
 "pa" -> "pan", "pa" -> "pap", "pa" -> "par", "pa" -> "pas", 
 "pa" -> "pat", "pa" -> "paw", "pa" -> "pay", "pa" -> "pea", 
 "pa" -> "spa", "ta" -> "eta", "ta" -> "tab", "ta" -> "tad", 
 "ta" -> "tag", "ta" -> "tam", "ta" -> "tan", "ta" -> "tap", 
 "ta" -> "tar", "ta" -> "tat", "ta" -> "tau", "ta" -> "tax", 
 "ta" -> "tea", "ya" -> "yak", "ya" -> "yam", "ya" -> "yap", 
 "ya" -> "yaw", "ya" -> "yea", "add" -> "adds", "ado" -> "dado", 
 "ads" -> "adds", "ads" -> "aids", "ads" -> "ands", "ads" -> "cads", 
 "ads" -> "dads", "ads" -> "fads", "ads" -> "gads", "ads" -> "lads", 
 "ads" -> "pads", "ads" -> "rads", "ads" -> "tads", "ads" -> "wads", 
 "aid" -> "acid", "aid" -> "aide", "aid" -> "aids", "aid" -> "amid", 
 "aid" -> "arid", "aid" -> "avid", "aid" -> "laid", "aid" -> "maid", 
 "aid" -> "paid", "aid" -> "raid", "aid" -> "said", "and" -> "ands", 
 "and" -> "band", "and" -> "hand", "and" -> "land", "and" -> "Land", 
 "and" -> "rand", "and" -> "Rand", "and" -> "sand", "and" -> "Sand", 
 "and" -> "wand", "bad" -> "bade", "bad" -> "bald", "bad" -> "band", 
 "bad" -> "bard", "bad" -> "baud", "bad" -> "bawd", "bad" -> "bead", 
 "bad" -> "brad", "cad" -> "cads", "cad" -> "card", "cad" -> "clad", 
 "cad" -> "scad", "dad" -> "dado", "dad" -> "dads", "dad" -> "dead", 
 "dad" -> "dyad", "fad" -> "fade", "fad" -> "fads", "gad" -> "egad", 
 "gad" -> "gads", "gad" -> "gawd", "gad" -> "glad", "gad" -> "goad", 
 "gad" -> "grad", "had" -> "Chad", "had" -> "hand", "had" -> "hard", 
 "had" -> "head", "had" -> "shad", "had" -> "Thad", "lad" -> "clad", 
 "lad" -> "glad", "lad" -> "lade", "lad" -> "lads", "lad" -> "lady", 
 "lad" -> "laid", "lad" -> "land", "lad" -> "lard", "lad" -> "laud", 
 "lad" -> "lead", "lad" -> "load", "lad" -> "Vlad", "mad" -> "made", 
 "mad" -> "maid", "mad" -> "mead", "pad" -> "pads", "pad" -> "paid", 
 "sad" -> "said", "sad" -> "sand", "sad" -> "scad", "sad" -> "shad", 
 "tad" -> "tads", "tad" -> "toad", "tad" -> "trad", "Tad" -> "Thad", 
 "wad" -> "wade", "wad" -> "wadi", "wad" -> "wads", "wad" -> "wand", 
 "wad" -> "ward", "wad" -> "woad", "aah" -> "ayah", "aha" -> "ahas", 
 "ash" -> "ashy", "ash" -> "bash", "ash" -> "cash", "ash" -> "Cash", 
 "ash" -> "dash", "ash" -> "gash", "ash" -> "hash", "ash" -> "lash", 
 "ash" -> "mash", "ash" -> "Nash", "ash" -> "rash", "ash" -> "sash", 
 "ash" -> "wash", "ash" -> "Wash", "bah" -> "bahs", "bah" -> "baht", 
 "bah" -> "bash", "bah" -> "bath", "bah" -> "blah", "pah" -> "path", 
 "rah" -> "rahs", "rah" -> "rash", "aim" -> "aims", "aim" -> "maim", 
 "amp" -> "amps", "amp" -> "camp", "amp" -> "damp", "amp" -> "lamp", 
 "amp" -> "ramp", "amp" -> "tamp", "amp" -> "vamp", "arm" -> "arms", 
 "arm" -> "army", "arm" -> "arum", "arm" -> "farm", "arm" -> "harm", 
 "arm" -> "warm", "cam" -> "calm", "cam" -> "came", "cam" -> "camp", 
 "cam" -> "cams", "cam" -> "clam", "cam" -> "cram", "cam" -> "scam", 
 "dam" -> "Adam", "dam" -> "dame", "dam" -> "damn", "dam" -> "damp", 
 "dam" -> "dams", "dam" -> "dram", "dam" -> "Edam", "ham" -> "hams", 
 "ham" -> "harm", "ham" -> "sham", "ham" -> "wham", "jam" -> "jamb", 
 "jam" -> "jams", "lam" -> "clam", "lam" -> "Elam", "lam" -> "flam", 
 "lam" -> "glam", "lam" -> "lama", "lam" -> "lamb", "lam" -> "lame", 
 "lam" -> "lamp", "lam" -> "lams", "lam" -> "loam", "lam" -> "slam", 
 "mam" -> "imam", "mam" -> "maim", "mam" -> "mama", "mam" -> "mams", 
 "ram" -> "cram", "ram" -> "dram", "ram" -> "gram", "ram" -> "pram", 
 "ram" -> "ramp", "ram" -> "rams", "ram" -> "ream", "ram" -> "roam", 
 "ram" -> "tram", "Sam" -> "Siam", "Sam" -> "Spam", "tam" -> "tame", 
 "tam" -> "tamp", "tam" -> "tams", "tam" -> "team", "tam" -> "tram", 
 "yam" -> "yams", "and" -> "ands", "and" -> "band", "and" -> "hand", 
 "and" -> "land", "and" -> "Land", "and" -> "rand", "and" -> "Rand", 
 "and" -> "sand", "and" -> "Sand", "and" -> "wand", "ans" -> "ands", 
 "ans" -> "ants", "ans" -> "anus", "ans" -> "awns", "ans" -> "bans", 
 "ans" -> "cans", "ans" -> "Dans", "ans" -> "fans", "ans" -> "Hans", 
 "ans" -> "Kans", "ans" -> "mans", "ans" -> "nans", "ans" -> "pans", 
 "ans" -> "sans", "ans" -> "tans", "ans" -> "vans", "ant" -> "ante", 
 "ant" -> "anti", "ant" -> "ants", "ant" -> "aunt", "ant" -> "cant", 
 "ant" -> "Kant", "ant" -> "pant", "ant" -> "rant", "ant" -> "want", 
 "any" -> "many", "any" -> "zany", "awn" -> "awns", "awn" -> "dawn", 
 "awn" -> "Dawn", "awn" -> "fawn", "awn" -> "lawn", "awn" -> "pawn", 
 "awn" -> "yawn", "ban" -> "band", "ban" -> "bane", "ban" -> "bang", 
 "ban" -> "bani", "ban" -> "bank", "ban" -> "bans", "ban" -> "barn", 
 "ban" -> "bean", "ban" -> "bran", "can" -> "cane", "can" -> "cans", 
 "can" -> "cant", "can" -> "clan", "can" -> "cyan", "can" -> "scan", 
 "can" -> "Scan", "Dan" -> "Dana", "Dan" -> "Dane", "Dan" -> "Dans", 
 "Dan" -> "Dawn", "Dan" -> "Dean", "fan" -> "fain", "fan" -> "fang", 
 "fan" -> "fans", "fan" -> "faun", "fan" -> "fawn", "fan" -> "flan", 
 "Han" -> "Hahn", "Han" -> "Hank", "Han" -> "Hans", "Ian" -> "Iran", 
 "Ian" -> "Ivan", "Jan" -> "Jain", "Jan" -> "Jana", "Jan" -> "Jane", 
 "Jan" -> "Jean", "Jan" -> "Joan", "Jan" -> "Juan", "Kan" -> "Kane", 
 "Kan" -> "Kano", "Kan" -> "Kans", "Kan" -> "Kant", "Kan" -> "Kean", 
 "Kan" -> "Khan", "Kan" -> "Klan", "man" -> "main", "man" -> "mane", 
 "man" -> "mans", "man" -> "many", "man" -> "mean", "man" -> "moan", 
 "man" -> "Oman", "Man" -> "Mani", "Man" -> "Mann", "Man" -> "Manx", 
 "nan" -> "nans", "pan" -> "pain", "pan" -> "pane", "pan" -> "pang", 
 "pan" -> "pans", "pan" -> "pant", "pan" -> "pawn", "pan" -> "plan", 
 "pan" -> "span", "pan" -> "Span", "ran" -> "bran", "ran" -> "Bran", 
 "ran" -> "Fran", "ran" -> "gran", "ran" -> "Iran", "ran" -> "Oran", 
 "ran" -> "rain", "ran" -> "rand", "ran" -> "rang", "ran" -> "rank", 
 "ran" -> "rant", "ran" -> "roan", "ran" -> "Tran", "San" -> "Sana", 
 "San" -> "Sand", "San" -> "Sang", "San" -> "Scan", "San" -> "Sean", 
 "San" -> "Span", "San" -> "Stan", "tan" -> "Stan", "tan" -> "tang", 
 "tan" -> "tank", "tan" -> "tans", "tan" -> "tarn", "tan" -> "than", 
 "van" -> "Evan", "van" -> "Ivan", "van" -> "vain", "van" -> "vane", 
 "van" -> "vans", "Van" -> "Vang", "wan" -> "swan", "wan" -> "wain", 
 "wan" -> "wand", "wan" -> "wane", "wan" -> "wank", "wan" -> "want", 
 "wan" -> "warn", "wan" -> "wean", "abs" -> "albs", "abs" -> "cabs", 
 "abs" -> "dabs", "abs" -> "gabs", "abs" -> "jabs", "abs" -> "labs", 
 "abs" -> "Labs", "abs" -> "nabs", "abs" -> "tabs", "ads" -> "adds", 
 "ads" -> "aids", "ads" -> "ands", "ads" -> "cads", "ads" -> "dads", 
 "ads" -> "fads", "ads" -> "gads", "ads" -> "lads", "ads" -> "pads", 
 "ads" -> "rads", "ads" -> "tads", "ads" -> "wads", "ans" -> "ands", 
 "ans" -> "ants", "ans" -> "anus", "ans" -> "awns", "ans" -> "bans", 
 "ans" -> "cans", "ans" -> "Dans", "ans" -> "fans", "ans" -> "Hans", 
 "ans" -> "Kans", "ans" -> "mans", "ans" -> "nans", "ans" -> "pans", 
 "ans" -> "sans", "ans" -> "tans", "ans" -> "vans", "ash" -> "ashy", 
 "ash" -> "bash", "ash" -> "cash", "ash" -> "Cash", "ash" -> "dash", 
 "ash" -> "gash", "ash" -> "hash", "ash" -> "lash", "ash" -> "mash", 
 "ash" -> "Nash", "ash" -> "rash", "ash" -> "sash", "ash" -> "wash", 
 "ash" -> "Wash", "ask" -> "asks", "ask" -> "bask", "ask" -> "cask", 
 "ask" -> "mask", "ask" -> "Sask", "ask" -> "task", "asp" -> "asap", 
 "asp" -> "asps", "asp" -> "gasp", "asp" -> "hasp", "asp" -> "rasp", 
 "asp" -> "wasp", "ass" -> "asks", "ass" -> "asps", "ass" -> "bass", 
 "ass" -> "Bass", "ass" -> "Kass", "ass" -> "lass", "ass" -> "mass", 
 "ass" -> "pass", "ass" -> "sass", "ass" -> "Tass", "gas" -> "gabs", 
 "gas" -> "gads", "gas" -> "gags", "gas" -> "gals", "gas" -> "gaps", 
 "gas" -> "gars", "gas" -> "gash", "gas" -> "gasp", "gas" -> "gays", 
 "has" -> "ahas", "has" -> "hags", "has" -> "hams", "has" -> "hash", 
 "has" -> "hasp", "has" -> "hast", "has" -> "hats", "has" -> "haws", 
 "has" -> "hays", "mas" -> "macs", "mas" -> "mags", "mas" -> "mams", 
 "mas" -> "mans", "mas" -> "maps", "mas" -> "mars", "mas" -> "mash", 
 "mas" -> "mask", "mas" -> "mass", "mas" -> "mast", "mas" -> "mats", 
 "mas" -> "maws", "mas" -> "Xmas", "pas" -> "pads", "pas" -> "pals", 
 "pas" -> "pans", "pas" -> "paps", "pas" -> "pars", "pas" -> "pass", 
 "pas" -> "past", "pas" -> "pats", "pas" -> "paws", "pas" -> "pays", 
 "pas" -> "peas", "pas" -> "spas", "was" -> "twas", "was" -> "wads", 
 "was" -> "wags", "was" -> "wars", "was" -> "wash", "was" -> "wasp", 
 "was" -> "wast", "was" -> "ways", "act" -> "acts", "act" -> "fact", 
 "act" -> "pact", "act" -> "tact", "aft" -> "daft", "aft" -> "haft", 
 "aft" -> "raft", "aft" -> "Taft", "aft" -> "waft", "ant" -> "ante", 
 "ant" -> "anti", "ant" -> "ants", "ant" -> "aunt", "ant" -> "cant", 
 "ant" -> "Kant", "ant" -> "pant", "ant" -> "rant", "ant" -> "want", 
 "apt" -> "rapt", "art" -> "arts", "art" -> "arty", "art" -> "Bart", 
 "art" -> "cart", "art" -> "dart", "art" -> "hart", "art" -> "Hart", 
 "art" -> "kart", "art" -> "mart", "art" -> "part", "art" -> "tart", 
 "art" -> "wart", "ate" -> "ante", "ate" -> "ates", "ate" -> "bate", 
 "ate" -> "date", "ate" -> "fate", "ate" -> "gate", "ate" -> "hate", 
 "ate" -> "Kate", "ate" -> "late", "ate" -> "mate", "ate" -> "Nate", 
 "ate" -> "pate", "ate" -> "Pate", "ate" -> "rate", "ate" -> "sate", 
 "ate" -> "Tate", "bat" -> "baht", "bat" -> "bait", "bat" -> "bast", 
 "bat" -> "bate", "bat" -> "bath", "bat" -> "bats", "bat" -> "beat", 
 "bat" -> "boat", "bat" -> "brat", "cat" -> "cant", "cat" -> "cart", 
 "cat" -> "cast", "cat" -> "cats", "cat" -> "chat", "cat" -> "coat", 
 "cat" -> "scat", "eat" -> "beat", "eat" -> "east", "eat" -> "eats", 
 "eat" -> "feat", "eat" -> "heat", "eat" -> "meat", "eat" -> "neat", 
 "eat" -> "peat", "eat" -> "seat", "eat" -> "teat", "fat" -> "fact", 
 "fat" -> "fast", "fat" -> "fate", "fat" -> "fats", "fat" -> "feat", 
 "fat" -> "fiat", "fat" -> "flat", "fat" -> "frat", "hat" -> "chat", 
 "hat" -> "ghat", "hat" -> "haft", "hat" -> "halt", "hat" -> "hart", 
 "hat" -> "hast", "hat" -> "hate", "hat" -> "hath", "hat" -> "hats", 
 "hat" -> "heat", "hat" -> "phat", "hat" -> "shat", "hat" -> "that", 
 "hat" -> "what", "mat" -> "malt", "mat" -> "mart", "mat" -> "mast", 
 "mat" -> "mate", "mat" -> "math", "mat" -> "mats", "mat" -> "meat", 
 "mat" -> "moat", "Nat" -> "Nate", "oat" -> "boat", "oat" -> "coat", 
 "oat" -> "goat", "oat" -> "moat", "oat" -> "oath", "oat" -> "oats", 
 "pat" -> "pact", "pat" -> "pant", "pat" -> "part", "pat" -> "past", 
 "pat" -> "pate", "pat" -> "path", "pat" -> "pats", "pat" -> "peat", 
 "pat" -> "phat", "pat" -> "prat", "pat" -> "spat", "Pat" -> "Pate", 
 "rat" -> "brat", "rat" -> "drat", "rat" -> "frat", "rat" -> "prat", 
 "rat" -> "raft", "rat" -> "rant", "rat" -> "rapt", "rat" -> "rate", 
 "rat" -> "rats", "sat" -> "salt", "sat" -> "sate", "sat" -> "scat", 
 "sat" -> "seat", "sat" -> "shat", "sat" -> "slat", "sat" -> "spat", 
 "sat" -> "swat", "tat" -> "tact", "tat" -> "tart", "tat" -> "tats", 
 "tat" -> "taut", "tat" -> "teat", "tat" -> "that", "vat" -> "vast", 
 "vat" -> "vats", "axe" -> "axed", "axe" -> "axes", "axe" -> "axle", 
 "fax" -> "flax", "lax" -> "flax", "Max" -> "Manx", "Max" -> "Marx", 
 "tax" -> "taxi", "wax" -> "waxy", "fab" -> "flab", "fad" -> "fade", 
 "fad" -> "fads", "fag" -> "fags", "fag" -> "fang", "fag" -> "flag", 
 "fan" -> "fain", "fan" -> "fang", "fan" -> "fans", "fan" -> "faun", 
 "fan" -> "fawn", "fan" -> "flan", "far" -> "afar", "far" -> "fair", 
 "far" -> "fare", "far" -> "farm", "far" -> "faro", "far" -> "fear", 
 "fat" -> "fact", "fat" -> "fast", "fat" -> "fate", "fat" -> "fats", 
 "fat" -> "feat", "fat" -> "fiat", "fat" -> "flat", "fat" -> "frat", 
 "fax" -> "flax", "fay" -> "fays", "fay" -> "flay", "fay" -> "fray", 
 "aha" -> "ahas", "had" -> "Chad", "had" -> "hand", "had" -> "hard", 
 "had" -> "head", "had" -> "shad", "had" -> "Thad", "hag" -> "hags", 
 "hag" -> "hang", "hag" -> "shag", "haj" -> "hajj", "ham" -> "hams", 
 "ham" -> "harm", "ham" -> "sham", "ham" -> "wham", "hap" -> "chap", 
 "hap" -> "harp", "hap" -> "hasp", "hap" -> "heap", "has" -> "ahas", 
 "has" -> "hags", "has" -> "hams", "has" -> "hash", "has" -> "hasp", 
 "has" -> "hast", "has" -> "hats", "has" -> "haws", "has" -> "hays", 
 "hat" -> "chat", "hat" -> "ghat", "hat" -> "haft", "hat" -> "halt", 
 "hat" -> "hart", "hat" -> "hast", "hat" -> "hate", "hat" -> "hath", 
 "hat" -> "hats", "hat" -> "heat", "hat" -> "phat", "hat" -> "shat", 
 "hat" -> "that", "hat" -> "what", "haw" -> "hawk", "haw" -> "haws", 
 "haw" -> "Shaw", "haw" -> "thaw", "hay" -> "hays", "hay" -> "hazy", 
 "hay" -> "shay", "lab" -> "blab", "lab" -> "flab", "lab" -> "labs", 
 "lab" -> "lamb", "lab" -> "slab", "lac" -> "lace", "lac" -> "lack", 
 "lac" -> "lacs", "lac" -> "lacy", "lad" -> "clad", "lad" -> "glad", 
 "lad" -> "lade", "lad" -> "lads", "lad" -> "lady", "lad" -> "laid", 
 "lad" -> "land", "lad" -> "lard", "lad" -> "laud", "lad" -> "lead", 
 "lad" -> "load", "lad" -> "Vlad", "lag" -> "blag", "lag" -> "flag", 
 "lag" -> "lags", "lag" -> "slag", "lam" -> "clam", "lam" -> "Elam", 
 "lam" -> "flam", "lam" -> "glam", "lam" -> "lama", "lam" -> "lamb", 
 "lam" -> "lame", "lam" -> "lamp", "lam" -> "lams", "lam" -> "loam", 
 "lam" -> "slam", "lap" -> "clap", "lap" -> "flap", "lap" -> "lamp", 
 "lap" -> "laps", "lap" -> "leap", "lap" -> "slap", "lav" -> "lava", 
 "lav" -> "lave", "lav" -> "lavs", "lav" -> "Olav", "lav" -> "Slav", 
 "law" -> "claw", "law" -> "flaw", "law" -> "lawn", "law" -> "laws", 
 "law" -> "slaw", "lax" -> "flax", "lay" -> "clay", "lay" -> "Clay", 
 "lay" -> "flay", "lay" -> "lacy", "lay" -> "lady", "lay" -> "lays", 
 "lay" -> "lazy", "lay" -> "play", "lay" -> "slay", "lea" -> "flea", 
 "lea" -> "ilea", "lea" -> "lead", "lea" -> "leaf", "lea" -> "leak", 
 "lea" -> "lean", "lea" -> "leap", "lea" -> "leas", "lea" -> "plea", 
 "Ola" -> "Olaf", "Ola" -> "Olav", "Ola" -> "Olga", "mac" -> "mace", 
 "mac" -> "mack", "mac" -> "macs", "mad" -> "made", "mad" -> "maid", 
 "mad" -> "mead", "mam" -> "imam", "mam" -> "maim", "mam" -> "mama", 
 "mam" -> "mams", "man" -> "main", "man" -> "mane", "man" -> "mans", 
 "man" -> "many", "man" -> "mean", "man" -> "moan", "man" -> "Oman", 
 "map" -> "maps", "mar" -> "mare", "mar" -> "mark", "mar" -> "marl", 
 "mar" -> "mars", "mar" -> "mart", "mar" -> "Omar", "mas" -> "macs", 
 "mas" -> "mags", "mas" -> "mams", "mas" -> "mans", "mas" -> "maps", 
 "mas" -> "mars", "mas" -> "mash", "mas" -> "mask", "mas" -> "mass", 
 "mas" -> "mast", "mas" -> "mats", "mas" -> "maws", "mas" -> "Xmas", 
 "mat" -> "malt", "mat" -> "mart", "mat" -> "mast", "mat" -> "mate", 
 "mat" -> "math", "mat" -> "mats", "mat" -> "meat", "mat" -> "moat", 
 "maw" -> "maws", "may" -> "many", "may" -> "mayo", "pad" -> "pads", 
 "pad" -> "paid", "pah" -> "path", "pal" -> "opal", "pal" -> "Opal", 
 "pal" -> "pail", "pal" -> "pale", "pal" -> "pall", "pal" -> "palm", 
 "pal" -> "pals", "pal" -> "pawl", "pal" -> "peal", "pan" -> "pain", 
 "pan" -> "pane", "pan" -> "pang", "pan" -> "pans", "pan" -> "pant", 
 "pan" -> "pawn", "pan" -> "plan", "pan" -> "span", "pan" -> "Span", 
 "pap" -> "papa", "pap" -> "paps", "par" -> "pair", "par" -> "para", 
 "par" -> "pare", "par" -> "park", "par" -> "pars", "par" -> "part", 
 "par" -> "pear", "par" -> "spar", "pas" -> "pads", "pas" -> "pals", 
 "pas" -> "pans", "pas" -> "paps", "pas" -> "pars", "pas" -> "pass", 
 "pas" -> "past", "pas" -> "pats", "pas" -> "paws", "pas" -> "pays", 
 "pas" -> "peas", "pas" -> "spas", "pat" -> "pact", "pat" -> "pant", 
 "pat" -> "part", "pat" -> "past", "pat" -> "pate", "pat" -> "path", 
 "pat" -> "pats", "pat" -> "peat", "pat" -> "phat", "pat" -> "prat", 
 "pat" -> "spat", "paw" -> "pawl", "paw" -> "pawn", "paw" -> "paws", 
 "pay" -> "pacy", "pay" -> "pays", "pay" -> "play", "pay" -> "pray", 
 "pay" -> "spay", "pea" -> "peak", "pea" -> "peal", "pea" -> "pear", 
 "pea" -> "peas", "pea" -> "peat", "pea" -> "plea", "spa" -> "spam", 
 "spa" -> "span", "spa" -> "spar", "spa" -> "spas", "spa" -> "spat", 
 "spa" -> "spay", "eta" -> "beta", "eta" -> "etas", "eta" -> "feta", 
 "eta" -> "Leta", "eta" -> "Meta", "eta" -> "zeta", "tab" -> "stab", 
 "tab" -> "tabs", "tad" -> "tads", "tad" -> "toad", "tad" -> "trad", 
 "tag" -> "stag", "tag" -> "tags", "tag" -> "tang", "tam" -> "tame", 
 "tam" -> "tamp", "tam" -> "tams", "tam" -> "team", "tam" -> "tram", 
 "tan" -> "Stan", "tan" -> "tang", "tan" -> "tank", "tan" -> "tans", 
 "tan" -> "tarn", "tan" -> "than", "tap" -> "tamp", "tap" -> "tape", 
 "tap" -> "taps", "tap" -> "tarp", "tap" -> "trap", "tar" -> "star", 
 "tar" -> "tare", "tar" -> "tarn", "tar" -> "taro", "tar" -> "tarp", 
 "tar" -> "tars", "tar" -> "tart", "tar" -> "tear", "tat" -> "tact", 
 "tat" -> "tart", "tat" -> "tats", "tat" -> "taut", "tat" -> "teat", 
 "tat" -> "that", "tau" -> "taus", "tau" -> "taut", "tax" -> "taxi", 
 "tea" -> "teak", "tea" -> "teal", "tea" -> "team", "tea" -> "tear", 
 "tea" -> "teas", "tea" -> "teat", "yak" -> "yaks", "yak" -> "yank", 
 "yam" -> "yams", "yap" -> "yaps", "yaw" -> "yawl", "yaw" -> "yawn", 
 "yaw" -> "yaws", "yea" -> "yeah", "yea" -> "year", "yea" -> "yeas"}

UPDATE

Just for fun (and using kguler's beautiful styling) for the "root" "a":

g[u_, n_] := NestList[Join @@ fun /@ Union[#[[All, 2]]] &, fun[u], n];
st[t_, l_] := {GraphLayout -> {"RadialEmbedding", "RootVertex" -> t}, 
   VertexStyle -> {_ :> White, (x_ /; StringLength[x] == l) -> 
      Directive[{Red, PointSize[.01]}], 
     t -> Directive[{Blue, PointSize[.01]}]}, 
   VertexLabels -> {Placed["Name", 
      Tooltip], (x_ /; StringLength[x] == l) -> 
      Placed[Style[x, Red, 12], {Tooltip, Before}]}, 
   VertexShapeFunction -> "Point", LabelStyle -> Red, 
   ImageSize -> 700, 
   EdgeStyle -> Directive[Opacity[.5], Hue[.15, .5, .8]], 
   Background -> Black, EdgeShapeFunction -> (Line[#1] &)};
With[{bas = g["a", 7]}, Manipulate[
  ve = Prepend[
    Through[{VertexCount, EdgeCount}[
        Graph[Join @@ bas[[1 ;; #]]]]] & /@ Range[8], {1, 0}];
  Column[{
    Row[{
      ListPlot[Transpose[ve], Joined -> True, Frame -> True, 
       PlotLegends -> {"Vertex Count", "EdgeCount"}, 
       FrameLabel -> {"Base string length", "Count"}, 
       ImageSize -> 250],
      ListPlot[Transpose[Differences@(ve)], Joined -> True, 
       Frame -> True, PlotLegends -> {"Vertex Count", "EdgeCount"}, 
       FrameLabel -> {"Base string length", "Change"}, 
       ImageSize -> 250]}],
    grp = Graph[Join @@ bas[[1 ;; s]], st["a", s + 1]]
    }],
  {s, Range[8]}]]

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Excellent. Yes... a single letter ANYWHERE in the word (including as a prefix or suffix). The graph actually thins out for words of length greater than 5. A clearer way to present the graph is TreePlot[Join @@ gr, Center]. $\endgroup$
    – David G. Stork
    Oct 15 '14 at 17:11
4
$\begingroup$

I am the original poser of this question which is not a homework question as belisarius could have realized by noting my identity. (Frankly, belisarius' statement that it was related to a homework problem he assigned did nothing to help me and others interested, and in fact apparently dissuaded others from addressing this problem. I grant that all would have been clearer had I shown my attempts.)

To wit: I addressed this problem with this function:

NewExpander::usage = "NewExpander[x] takes a string x and produces a list of all valid English words formed by inserting a single letter in every possible slot in x, e.g., NewExpander['cat'] = {'cat',{'cant','cart','cast','cats','chat','coat','scat'}}";
NewExpander[x_: String] := {x, Select[
    Union@
     Flatten@Table[
       StringInsert[x, #, ll] & /@ CharacterRange["a", "z"], {ll, 1, 
        StringLength[StringTake[x, -1]] + 1}],
     DictionaryLookup[#] != {} &]} /; Depth[x] == 1

Then I wrote code to convert the output of NewExpander[ ] into the list of links from the source word to each of the descendant words using Outer[ ]:

Flatten[Outer[
    Rule, {#[[1]]}, #[[2]]] & /@ {{"a", {"ad", "ah", "am", "an", "as",
      "at", "ax", "fa", "ha", "la", "ma", "pa", "ta", 
     "ya"}}, {"i", {"bi", "hi", "id", "if", "in", "is", "it", "mi", 
     "oi", "pi", "ti", "xi"}}}, \[Infinity]]

This is useful for creating a list of links to be used by TreeGraph[ ].

The problem was then nesting the NewExpander[ ] code so that it iteratively expanded only the deepest levels in the resulting list and keeping all the nesting levels organized, as needed by the problem.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.