From: Thane Plambeck <thane@best.com>

Subject: Re: [math-fun] An Amazing Anagram

I fail to see what examples of simple anagrams, and the Shakespeare one that came before it, have to do with maths. For those desperate for anagrams related to the 2004 election, I started a thread in a location where anagrams are not off-topic, in fact they _are_ the topic - the newsgroup alt.anagrams - findable at your local newsserver, with the subject line "RFG (request for grams) - 2004 election" or at: http://groups.google.com/groups?threadm=873c1jux5d.fsf%40nonospaz.fatphil.or... Please feel free to join in there. (Although the base phrase was changed slightly, do check out Rick Rothstein's reply.) However, anagrams and mathematics are not entirely unrelated. For example there are interesting combinatorial algorithms related to anagrams, as demonsrated in recent years by Noam Elkies and others (historically Mike Keith has had a mathematical bent and tackled similar ideas too). In particular, given sets of phrases S = { s0, s1, .... sm }, T = { t0, t1, ... tn }, find the substets S', T' of S and T respectively such that S' ~ T' (where '~' is the anagram equivalence operator). Or, given one set of phrases S = { s0, s1, ... sn }, find two disjoint subsets S', T', of S such that S' ~ T'. For small sets, in particular if S' and T' are deliberately to be kept small (thus reducing the chance of finding anagrams) the combinatorial expansion is quite manageable. For example Noam's ITALY + GABON = LIBYA + TONGA BELARUS + INDIA = LIBERIA + SUDAN would drop out quite quickly as there are <10^5 country name pairs. For larger sets, the combinatorial explosion guarantees a vast number of results, but the sparseness means that a naive brute-force search would be unlikely to find any. e.g. Noam's http://groups.google.com/groups?selm=abchdf%24up8%241%40news.fas.harvard.edu cannot be found by just chance. On another mathematical note - algorithms for finding anagrams can be applied to the problem of finding amicable pairs! (Just with a theoretically infinite-sized alphabet, but we're mathematicians, and that shouldn't scare us, surely?) Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com