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.

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