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

 Four Letter Sequences (Posted on 2005-01-12)
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.)
 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)
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

 Search: Search body:
Forums (0)