All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General > Word Problems
Four Letter Sequences (Posted on 2005-01-12) Difficulty: 3 of 5
A sequence of letters is considered "valid" if it occurs as a substring of a common English word. For example, "RGRO" is valid because it occurs in the word "undeRGROund."

Find a sequence of four distinct letters such that all 23 non-identity permutations of the sequence are valid.

See The Solution Submitted by David Shin    
Rating: 3.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Computer Solution | Comment 4 of 8 |

Computer solution was a 3-phase process: creating a 14,950 x 24 array, of 14,950 combinations of 26 letters taken at a time by the 24 permutations of each and setting it for each 4-letter grouping in a word list; finding those columns (combinations) in which at least 23 permutations had been marked as used; and going throug the dictionary again, listing the words that had those combinations.

The trickiest part is finding an algorithm to find an enumeration of a combination number for any combination of letters, to use as a subscript.  The system that makes the most sense is to enumerate them alphabetically by the alphabetized version of the combination, so for example, ABCD, or CBDA, etc., would be combination #1, ABCE or BAEC, etc. would be combination #2, etc., ... , WXYZ or ZXYW, etc. would be combination number 14,950. Or they could be numbered 0 - 14,949 in a zero-based system.  The following algorithm does that. It first alphabetizes the four letters. Then it goes through the entire alphabet, except for Z and for each letter, if it is not present in the group of four adds in the combinations of the remaining letters of the alphabet for the remaining letters in the group.  For example, for BEGH:

Position to first letter of alphabet and first letter of set of four.
A add in C(25,3), for 25 letters remaining in alphabet and 3 remaining in group.
B This is present in group--just advance to next letter, the E, within the group of four.
C add in C(23,2), for 23 letters of alphabet after C and 2 letters in group of four after E.
D add in C(22,2), for 22 letters of alphabet after D and 2 letters in group of four after E.
E just skip to next letter, G in group (F in alphabet)
F add in C(20,1)
G just skip to next letter
H just skip to next letter
I and beyond-- all zero as combinations exhausted

So this case gives C(23,2)+C(22,2)+C(20,1)=504

This is zero based as it counts the number of combinations that precede the one in question.

FUNCTION combNo (st$)
  'combination numbers for UNIQUELY lettered strings (no repeated letters)
  bse = ASC("a") - 1
  s$ = st$
  tot = 0
  DO
    sw = 0
    FOR p = 1 TO LEN(st$) - 1
     IF MID$(s$, p, 1) > MID$(s$, p + 1, 1) THEN
       h$ = MID$(s$, p, 1)
       MID$(s$, p, 1) = MID$(s$, p + 1, 1)
       MID$(s$, p + 1, 1) = h$
       sw = 1
     END IF
    NEXT
  LOOP UNTIL sw = 0
  numAft = 25: posAft = LEN(st$) - 1: p = 1
  lp$ = MID$(s$, p, 1): aVal = ASC(lp$) - bse
  FOR lt = 1 TO 25
   IF lt < aVal THEN
    tot = tot + comb(26 - lt, posAft)
   ELSE
    posAft = posAft - 1
    p = p + 1
    IF p > LEN(s$) THEN EXIT FOR
    lp$ = MID$(s$, p, 1): aVal = ASC(lp$) - bse
   END IF
  NEXT lt
  combNo = tot
END FUNCTION

The program found 23 valid sequences in different order for AIDR (that being the order not found), but several of these were found only in uncommon words.  The same is true of AERT and NIAG (Niagara being capitalized doesn't count, so that's the odd order out).

IART seems to be the combination sought.  This particular order occurs only in unusual words like ANTIARTHRITIC.  All 23 other orders appear in various common words, like TRIANGLE, LOGARITHM and RATIO.

ITSA also appears in all 24 permutations, but several of those are found only in uncommon words.

Obviously the weeding out of uncommon words was done by hand.

The following list shows, for IART, the common words found, plus the representative for IART itself, marked with an asterisk.  The columns are the 1585, which is the number of the combination, then the number of the permutation, then 24 indicating its part of 24 permutations found, the sequence that is that permutation, and the word itself:

  1585  0 24 airt airtight             
  1585  0 24 airt airtime             
  1585  1 24 aitr waitress            
  1585  2 24 arit angularity          
  1585  2 24 arit apparition          
  1585  2 24 arit apparitional        
  1585  2 24 arit apparitions         
  1585  2 24 arit arithmetic          
  1585  2 24 arit barbarity           
  1585  2 24 arit baritone            
  1585  2 24 arit binocularity        
  1585  2 24 arit bipolarity          
  1585  2 24 arit capillarity         
  1585  2 24 arit charitable          
  1585  2 24 arit charity             
  1585  2 24 arit circularity         
  1585  2 24 arit clarity             
  1585  2 24 arit complementarity     
  1585  2 24 arit cryptarithm         
  1585  2 24 arit disparity           
  1585  2 24 arit dissimilarity       
  1585  2 24 arit extramarital        
  1585  2 24 arit familiarity         
  1585  2 24 arit granularity         
  1585  2 24 arit hilarity            
  1585  2 24 arit jocularity          
  1585  2 24 arit linearity           
  1585  2 24 arit logarithm           
  1585  2 24 arit margarita           
  1585  2 24 arit marital             
  1585  2 24 arit maritime            
  1585  2 24 arit modularity          
  1585  2 24 arit molarity            
  1585  2 24 arit multicellularity    
  1585  2 24 arit parity              
  1585  2 24 arit peculiarity         
  1585  2 24 arit perpendicularity    
  1585  2 24 arit polarity            
  1585  2 24 arit popularity          
  1585  2 24 arit postmarital         
  1585  2 24 arit premarital          
  1585  2 24 arit rarity              
  1585  2 24 arit regularity          
  1585  2 24 arit samaritan           
  1585  2 24 arit similarity          
  1585  2 24 arit singularity         
  1585  2 24 arit solidarity          
  1585  2 24 arit sybaritic           
  1585  2 24 arit uncharitable        
  1585  2 24 arit unfamiliarity       
  1585  2 24 arit vulgarity           
  1585  3 24 arti artichoke           
  1585  3 24 arti article             
  1585  3 24 arti articulate          
  1585  3 24 arti artier              
  1585  3 24 arti artifact            
  1585  3 24 arti artifice            
  1585  3 24 arti artificiality       
  1585  3 24 arti artillery           
  1585  3 24 arti artily              
  1585  3 24 arti artiness            
  1585  3 24 arti artisan             
  1585  3 24 arti artist              
  1585  3 24 arti bipartisan          
  1585  3 24 arti cartilage           
  1585  3 24 arti carting             
  1585  3 24 arti cathartic           
  1585  3 24 arti charting            
  1585  3 24 arti darting             
  1585  3 24 arti departing           
  1585  3 24 arti disarticulate       
  1585  3 24 arti farting             
  1585  3 24 arti flowcharting        
  1585  3 24 arti heartier            
  1585  3 24 arti heartily            
  1585  3 24 arti impartial           
  1585  3 24 arti imparting           
  1585  3 24 arti martial             
  1585  3 24 arti martin              
  1585  3 24 arti martinet            
  1585  3 24 arti martingale          
  1585  3 24 arti martingales         
  1585  3 24 arti martini             
  1585  3 24 arti outsmarting         
  1585  3 24 arti partial             
  1585  3 24 arti participant         
  1585  3 24 arti participate         
  1585  3 24 arti participle          
  1585  3 24 arti particle            
  1585  3 24 arti particular          
  1585  3 24 arti particulates        
  1585  3 24 arti parties             
  1585  3 24 arti parting             
  1585  3 24 arti partisan            
  1585  3 24 arti partition           
  1585  3 24 arti quartic             
  1585  3 24 arti quartile            
  1585  3 24 arti smartie             
  1585  3 24 arti smarting            
  1585  3 24 arti starting            
  1585  3 24 arti tartish             
  1585  3 24 arti thwarting           
  1585  3 24 arti wartier             
  1585  3 24 arti wartime             
  1585  4 24 atir satire              
  1585  5 24 atri atrium              
  1585  5 24 atri aviatrix            
  1585  5 24 atri cockatrice          
  1585  5 24 atri compatriot          
  1585  5 24 atri diatribe            
  1585  5 24 atri dominatrix          
  1585  5 24 atri expatriate          
  1585  5 24 atri fratricide          
  1585  5 24 atri generatrix          
  1585  5 24 atri geriatric           
  1585  5 24 atri idolatries          
  1585  5 24 atri latrine             
  1585  5 24 atri matriarch           
  1585  5 24 atri matricide           
  1585  5 24 atri matriculate         
  1585  5 24 atri matrimony           
  1585  5 24 atri matrix              
  1585  5 24 atri patriarch           
  1585  5 24 atri patrician           
  1585  5 24 atri patricide           
  1585  5 24 atri patrimony           
  1585  5 24 atri patriot             
  1585  5 24 atri pediatrician        
  1585  5 24 atri podiatrist          
  1585  5 24 atri psychiatrist        
  1585  5 24 atri repatriate          
  1585  5 24 atri theatric            
  1585  6 24 iart antiarthritic        *
  1585  7 24 iatr aviatrix            
  1585  7 24 iatr diatribe            
  1585  7 24 iatr geriatric           
  1585  7 24 iatr pediatrician        
  1585  7 24 iatr podiatrist          
  1585  7 24 iatr psychiatrist        
  1585  8 24 irat admiration          
  1585  8 24 irat aspirate            
  1585  8 24 irat conspirator         
  1585  8 24 irat emirate             
  1585  8 24 irat expiration          
  1585  8 24 irat inspiration         
  1585  8 24 irat irate               
  1585  8 24 irat perspiration        
  1585  8 24 irat pirate              
  1585  8 24 irat respiration         
  1585  8 24 irat transpiration       
  1585  9 24 irta flirtation          
  1585 10 24 itar authoritarian       
  1585 10 24 itar communitarian       
  1585 10 24 itar demilitarize        
  1585 10 24 itar dignitary           
  1585 10 24 itar egalitarian         
  1585 10 24 itar guitar              
  1585 10 24 itar hereditary          
  1585 10 24 itar humanitarian        
  1585 10 24 itar majoritarian        
  1585 10 24 itar military            
  1585 10 24 itar pituitary           
  1585 10 24 itar sanitarium          
  1585 10 24 itar sanitary            
  1585 10 24 itar scimitar            
  1585 10 24 itar sitar               
  1585 10 24 itar solitary            
  1585 10 24 itar totalitarian        
  1585 10 24 itar trinitarian         
  1585 10 24 itar uniformitarian      
  1585 10 24 itar unitary             
  1585 10 24 itar utilitarian         
  1585 11 24 itra arbitrage           
  1585 11 24 itra arbitrary           
  1585 11 24 itra arbitrate           
  1585 11 24 itra nitrate             
  1585 11 24 itra recalcitrant        
  1585 11 24 itra semitrailer         
  1585 11 24 itra titrate             
  1585 12 24 rait portrait            
  1585 12 24 rait strait              
  1585 12 24 rait straitjacket        
  1585 12 24 rait straitlaced         
  1585 12 24 rait straits             
  1585 12 24 rait trait               
  1585 12 24 rait traitor             
  1585 12 24 rait wraith              
  1585 13 24 rati aberration          
  1585 13 24 rati abjuration          
  1585 13 24 rati accelerating        
  1585 13 24 rati administration      
  1585 13 24 rati admiration          
  1585 13 24 rati adoration           
  1585 13 24 rati adulteration        
  1585 13 24 rati aeration            
  1585 13 24 rati alliterative        
  1585 13 24 rati alteration          
  1585 13 24 rati ameliorating        
  1585 13 24 rati arbitrating         
  1585 13 24 rati aristocratic        
  1585 13 24 rati aspiration          
  1585 13 24 rati autocratic          
  1585 13 24 rati berating            
  1585 13 24 rati bureaucratic        
  1585 13 24 rati calibrating         
  1585 13 24 rati castrati            
  1585 13 24 rati castration          
  1585 13 24 rati celebration         
  1585 13 24 rati collaboration       
  1585 13 24 rati coloration          
  1585 13 24 rati commemoration       
  1585 13 24 rati commiserating       
  1585 13 24 rati comparative         
  1585 13 24 rati concentration       
  1585 13 24 rati confederation       
  1585 13 24 rati configuration       
  1585 13 24 rati conflagration       
  1585 13 24 rati conglomeration      
  1585 13 24 rati consecration        
  1585 13 24 rati consideration       
  1585 13 24 rati cooperation         
  1585 13 24 rati corporation         
  1585 13 24 rati corroboration       
  1585 13 24 rati crating             
  1585 13 24 rati curative            
  1585 13 24 rati decelerating        
  1585 13 24 rati declaration         
  1585 13 24 rati decoration          
  1585 13 24 rati degeneration        
  1585 13 24 rati dehydration         
  1585 13 24 rati deliberation        
  1585 13 24 rati democratic          
  1585 13 24 rati demonstration       
  1585 13 24 rati desecration         
  1585 13 24 rati desperation         
  1585 13 24 rati deterioration       
  1585 13 24 rati discoloration       
  1585 13 24 rati disintegration      
  1585 13 24 rati duration            
  1585 13 24 rati elaboration         
  1585 13 24 rati emigration          
  1585 13 24 rati enumeration         
  1585 13 24 rati erratic             
  1585 13 24 rati evaporation         
  1585 13 24 rati eviscerating        
  1585 13 24 rati exaggeration        
  1585 13 24 rati exasperation        
  1585 13 24 rati exhilaration        
  1585 13 24 rati exoneration         
  1585 13 24 rati expectoration       
  1585 13 24 rati expiration          
  1585 13 24 rati exploration         
  1585 13 24 rati federation          
  1585 13 24 rati filtration          
  1585 13 24 rati frustration         
  1585 13 24 rati generation          
  1585 13 24 rati gratification       
  1585 13 24 rati grating             
  1585 13 24 rati gratis              
  1585 13 24 rati gratitude           
  1585 13 24 rati gyration            
  1585 13 24 rati idiosyncratic       
  1585 13 24 rati illustration        
  1585 13 24 rati immigration         
  1585 13 24 rati imperative          
  1585 13 24 rati inauguration        
  1585 13 24 rati incarceration       
  1585 13 24 rati incineration        
  1585 13 24 rati infiltration        
  1585 13 24 rati ingratiate          
  1585 13 24 rati inspiration         
  1585 13 24 rati integration         
  1585 13 24 rati invigorating        
  1585 13 24 rati irrational          
  1585 13 24 rati iteration           
  1585 13 24 rati laceration          
  1585 13 24 rati liberation          
  1585 13 24 rati lucrative           
  1585 13 24 rati maturation          
  1585 13 24 rati mensuration         
  1585 13 24 rati migration           
  1585 13 24 rati ministration       
  1585 13 24 rati moderation          
  1585 13 24 rati narration           
  1585 13 24 rati numeration          
  1585 13 24 rati obliterating        
  1585 13 24 rati operatic            
  1585 13 24 rati operation           
  1585 13 24 rati oration             
  1585 13 24 rati orchestration       
  1585 13 24 rati pejorative          
  1585 13 24 rati penetration         
  1585 13 24 rati perforation         
  1585 13 24 rati perpetrating        
  1585 13 24 rati perspiration        
  1585 13 24 rati postoperatively     
  1585 13 24 rati prating             
  1585 13 24 rati preoperative        
  1585 13 24 rati preparation         
  1585 13 24 rati proliferation       
  1585 13 24 rati prorating           
  1585 13 24 rati quadratic           
  1585 13 24 rati ratification        
  1585 13 24 rati ratify              
  1585 13 24 rati rating              
  1585 13 24 rati ratio               
  1585 13 24 rati ration              
  1585 13 24 rati rational            
  1585 13 24 rati rationale           
  1585 13 24 rati rationalize         
  1585 13 24 rati remonstration       
  1585 13 24 rati remuneration        
  1585 13 24 rati respiration         
  1585 13 24 rati restoration         
  1585 13 24 rati reverberation       
  1585 13 24 rati saturation          
  1585 13 24 rati separation          
  1585 13 24 rati sequestration       
  1585 13 24 rati serration           
  1585 13 24 rati stratification      
  1585 13 24 rati theocratic          
  1585 13 24 rati toleration          
  1585 13 24 rati transliteration     
  1585 13 24 rati ulceration          
  1585 13 24 rati veneration          
  1585 13 24 rati vituperation        
  1585 14 24 riat appropriate         
  1585 14 24 riat bivariate           
  1585 14 24 riat excoriate           
  1585 14 24 riat expatriate          
  1585 14 24 riat expropriate         
  1585 14 24 riat geriatric           
  1585 14 24 riat inappropriate       
  1585 14 24 riat inebriated          
  1585 14 24 riat infuriate           
  1585 14 24 riat lariat              
  1585 14 24 riat luxuriate           
  1585 14 24 riat multivariate        
  1585 14 24 riat proletariat         
  1585 14 24 riat repatriate          
  1585 14 24 riat variate             
  1585 14 24 riat variation           
  1585 15 24 rita authoritarian       
  1585 15 24 rita authoritative       
  1585 15 24 rita charitable          
  1585 15 24 rita extramarital        
  1585 15 24 rita heritable           
  1585 15 24 rita heritage            
  1585 15 24 rita irritable           
  1585 15 24 rita marital             
  1585 15 24 rita premarital          
  1585 15 24 rita puritanical         
  1585 15 24 rita samaritan           
  1585 15 24 rita veritable           
  1585 16 24 rtai appertain           
  1585 16 24 rtai ascertain           
  1585 16 24 rtai certain             
  1585 16 24 rtai curtail             
  1585 16 24 rtai curtain             
  1585 16 24 rtai entertain           
  1585 16 24 rtai pertain             
  1585 17 24 rtia impartial           
  1585 17 24 rtia inertia             
  1585 17 24 rtia martial             
  1585 17 24 rtia partial             
  1585 17 24 rtia tertiary            
  1585 18 24 tair downstairs          
  1585 18 24 tair solitaire           
  1585 18 24 tair stair               
  1585 19 24 tari authoritarian       
  1585 19 24 tari commentaries        
  1585 19 24 tari communitarian       
  1585 19 24 tari complementaries     
  1585 19 24 tari cryptarithm         
  1585 19 24 tari demilitarization    
  1585 19 24 tari distributaries      
  1585 19 24 tari documentaries       
  1585 19 24 tari egalitarian         
  1585 19 24 tari guitarist           
  1585 19 24 tari involuntarily       
  1585 19 24 tari libertarian         
  1585 19 24 tari militarily          
  1585 19 24 tari momentarily         
  1585 19 24 tari nectarine           
  1585 19 24 tari notaries            
  1585 19 24 tari notarization        
  1585 19 24 tari parliamentarian     
  1585 19 24 tari pituitaries         
  1585 19 24 tari planetarium         
  1585 19 24 tari proletariat         
  1585 19 24 tari rotaries            
  1585 19 24 tari rudimentarily       
  1585 19 24 tari sanitarium          
  1585 19 24 tari secretarial         
  1585 19 24 tari sectarian           
  1585 19 24 tari sitarist            
  1585 19 24 tari solitarily          
  1585 19 24 tari staring             
  1585 19 24 tari tariff              
  1585 19 24 tari totalitarian        
  1585 19 24 tari tributaries         
  1585 19 24 tari trinitarian         
  1585 19 24 tari uniformitarian      
  1585 19 24 tari unitarian           
  1585 19 24 tari utilitarian         
  1585 19 24 tari vegetarian          
  1585 19 24 tari voluntarily         
  1585 20 24 tiar bestiary            
  1585 20 24 tiar evidentiary         
  1585 20 24 tiar penitentiary        
  1585 20 24 tiar tertiary            
  1585 20 24 tiar tiara               
  1585 21 24 tira tirade              
  1585 21 24 tira tiramisu            
  1585 22 24 trai constrain           
  1585 22 24 trai contrail            
  1585 22 24 trai contraindicate      
  1585 22 24 trai entrails            
  1585 22 24 trai entrain             
  1585 22 24 trai eyestrain           
  1585 22 24 trai portrait            
  1585 22 24 trai quatrain            
  1585 22 24 trai restrain            
  1585 22 24 trai semitrailer         
  1585 22 24 trai straight            
  1585 22 24 trai strain              
  1585 22 24 trai strait              
  1585 22 24 trai trail               
  1585 22 24 trai train               
  1585 22 24 trai traipse             
  1585 22 24 trai trait               
  1585 22 24 trai traitor             
  1585 23 24 tria atria               
  1585 23 24 tria atrial              
  1585 23 24 tria equestrian          
  1585 23 24 tria expatriate          
  1585 23 24 tria extraterrestrial    
  1585 23 24 tria industrial          
  1585 23 24 tria matriarch           
  1585 23 24 tria mistrial            
  1585 23 24 tria nutria              
  1585 23 24 tria patriarch           
  1585 23 24 tria pedestrian          
  1585 23 24 tria repatriate          
  1585 23 24 tria striation           
  1585 23 24 tria terrestrial         
  1585 23 24 tria triad               
  1585 23 24 tria triage              
  1585 23 24 tria trial               
  1585 23 24 tria triangle            
  1585 23 24 tria triathlon           
  1585 23 24 tria triathlons          
  1585 23 24 tria triatomic           
  1585 23 24 tria triaxial            
  1585 23 24 tria triaxialities       
  1585 23 24 tria triaxiality         
  1585 23 24 tria unindustrialized    

  Posted by Charlie on 2005-01-13 02:47:23
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information