Regex for all 10 letter words, with unique letters

Question

I am trying to write a regex that will display all words that are 10 characters long, and none of the letters are repeating.

So far, I have got

grep --colour -Eow '(\w{10})'

Which is the very first part of the question. How would I go about checking for the "uniqueness"? I really don't have a clue, apart from that I need to use back references.

Answer 1

grep -Eow '\w{10}' | grep -v '\(.\).*\1'

excludes words that have two identical characters.

grep -Eow '\w{10}' | grep -v '\(.\)\1'

excludes the ones that have repeating characters.

POSIXly:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -xE '.{10}' |
   grep -v '\(.\).*\1'

tr puts words on their own line by converting any sequence of non-word-characters (complement of alpha-numeric and underscore) to a newline character.

Or with one grep:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -ve '^.\{0,9\}$' -e '.\{11\}' -e '\(.\).*\1'

(exclude lines of less than 10 and more than 10 characters and those with a character appearing at least twice).

With one grep only (GNU grep with PCRE support or pcregrep):

grep -Po '\b(?:(\w)(?!\w*\1)){10}\b'

That is, a word boundary (\b) followed by a sequence of 10 word characters (provided that each is not followed by a sequence of word characters and themselves, using the negative look-ahead PCRE operator (?!...)).

We're lucky that it works here, as not many regexp engines work with backreferences inside repeating parts.

Note that (with my version of GNU grep at least)

grep -Pow '(?:(\w)(?!\w*\1)){10}'

Doesn't work, but

grep -Pow '(?:(\w)(?!\w*\2)){10}'

does (as echo aa | grep -Pw '(.)\2') which sounds like a bug.

You may want:

grep -Po '(*UCP)\b(?:(\w)(?!\w*\1)){10}\b'

if you want \w or \b to consider any letter as a word component and not just the ASCII ones in non-ASCII locales.

Another alternative:

grep -Po '\b(?!\w*(\w)\w*\1)\w{10}\b'

That is a word boundary (one that is not followed by a sequence of word characters one of which repeats) followed by 10 word characters.

Things to possibly have at the back of one's mind:

• Comparison is case sensitive, so Babylonish for instance would be matched, since all the characters are different even though there are two Bs, one lower and one upper case (use -i to change that).
• for -w, \w and \b, a word is a letter (ASCII ones only for GNU grep for now, the [:alpha:] character class in your locale if using -P and (*UCP)), decimal digits or underscore.
• that means that c'est (two words as per the French definition of a word) or it's (one word according to some English definitions of a word) or rendez-vous (one word as per the French definition of a word) are not considered one word.
• Even with (*UCP), Unicode combining characters are not considered as word components, so téléphone ($'t\u00e9le\u0301phone') is considered as 10 characters, one of which non-alpha. défavorisé ($'d\u00e9favorise\u0301') would be matched even though it's got two é because that's 10 all different alpha characters followed by a combining acute accent (non-alpha, so there's a word boundary between the e and its accent).

Answer 2

Okay...here's the clunky way for a five character string:

grep -P '^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4).$'

Because you cannot put a back reference in a character class (e.g. [^\1|\2]), you must use a negative look-ahead -- (?!foo). This is a PCRE feature so you need the -P switch.

The pattern for a 10 character string will be a lot longer, of course, but there is a shorter method using a variable length anything match ('.*') in the lookahead:

grep -P '^(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!.*\4)(.)(?!.*\5).$'

---

After reading Stephane Chazelas's enlightening answer, I realized there is a similar simple pattern for this usable via grep's -v switch:

    (.).*\1

Since the check proceeds one character at a time, this will see if any given character is followed by zero or more characters (.*) and then a match for the back reference. -v inverts, printing only things which don't match this pattern. This makes the back references more useful since they can't be negated with a character class, and significantly:

grep -v '\(.\).*\1'

will work to identify a string of any length with unique characters whereas:

grep -P '(.)(?!.*\1)'

will not, since it will match whatever suffix with unique characters (e.g. abcabc matches because of abc at the end, and aaaa because of a at the end -- hence any string). This is a complication caused by lookarounds being zero-width (they do not consume anything).

Answer 3

If you don't need to do the whole thing in regex, I would do it on two steps: first match all 10-letter words, then filter them for uniqueness. The shortest way I know how to do this is in Perl:

perl -nle 'MATCH:while(/\W(\w{10})\W/g){
             undef %seen;
             for(split//,$1){next MATCH if ++$seen{$_} > 1}
             print
           }' your_file

Note the additional \W anchors to ensure that only words that are exactly 10 characters long are matched.

Answer 4

Others have suggested this is not possible without various extensions to certain regular expression systems that are not in fact regular. However, since the language you want to match is finite, it's clearly regular. For 3 letters from a 4-letter alphabet, it would be easy:

(abc|abd|acb|acd|bac|bad|bcd|bdc|cab|cad|cbd|cdb|dab|dac|dbc|dcb)

Obviously this gets out of hand in a hurry with more letters and larger alphabets. :-)

Answer 5

Option --perl-regexp (short -P) of GNU grep uses more powerful regular expressions that include look ahead patterns. The following pattern looks for each letter that this letter does not appear in the remainder of the word:

grep -Pow '((\w)(?!\w*\g{-1})){10}'

However the run-time behavior is quite bad, because \w* can have nearly infinite length. It can be limited to \w{,8}, but that also checks beyond the word limit of 10 letters. Therefore the following pattern first checks the correct word length:

grep -Pow '(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}'

As test file I have used a large ≈ 500 MB file:

• First pattern: ≈ 43 s
• Latter pattern: ≈ 15 s

Update:

I couldn't find a significant change in the run-time behavior for a non-greedy operator (\w*?) or possessive operator ((...){10}+). A tiny bit faster seems the replacement of option -w:

grep -Po '\b(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}\b'

An update of grep from version 2.13 to 2.18 was much more effective. The test file only took ≈ 6 s.

Answer 6

A Perl solution:

perl -lne 'print if (!/(.)(?=$1)/g && /^\w{10}$/)' file

but it doesnt work with

perl -lne 'print if (!/(.)(?=\1)/g && /^\w{10}$/)' file

or

perl -lne 'print if ( /(.)(?!$1)/g && /^\w{10}$/)' file

tested with perl v5.14.2 and v5.18.2