23

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.

18
  • 1
    This must be done with a regex? Feb 22, 2014 at 16:44
  • I am practising regex, so preferably yes :) Feb 22, 2014 at 16:53
  • 3
    I don't believe you can do this with a computer-science style regular expression: what you want requires "memory" of what the preceding matched characters are, and regular expressions just don't have that. That said, you might be able to do it with back references and the non-regular-expression things that PCRE-style matching can do.
    – user732
    Feb 22, 2014 at 17:34
  • 3
    @BruceEdiger as long as there are a finite number of characters in the language (26) and letters in the string (10), its quite possible to do. Its just a lot of states, but nothing that would make it not a regular language.
    – user46212
    Feb 23, 2014 at 0:54
  • 1
    Do you mean "All English words ..."? Do you mean to include those spelled with hyphens and apostrophes or not (in-law, don't)? Do you mean to include words such as café, naïve, façade? Feb 23, 2014 at 1:27

6 Answers 6

41
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).
11
  • 1
    Awesome. \w does not match - though.
    – Graeme
    Feb 22, 2014 at 19:04
  • @Stephane Can you post a brief explanation of last two expressions. Feb 22, 2014 at 21:14
  • Sometimes it seems like lookarounds are the solution to all the things that used to be impossible with RE.
    – Barmar
    Feb 23, 2014 at 3:15
  • 1
    @Barmar they're still impossible with Regular Expressions. A "Regular Expression" is a mathematical construct that explicitly only allows certain constructs, namely literal characters, character classes, and the '|', '(...)', '?', '+' and '*' operators. Any so-called "regular expression" that uses an operator that is not one of the above is not actually a Regular Expression.
    – Jules
    Feb 23, 2014 at 7:15
  • 1
    @Jules This is unix.stackexchange.com, not math.stackexchange.com. The mathematical RE's are irrelevant in this context, we're talking about the kinds of REs you use with grep, PCRE, etc.
    – Barmar
    Feb 23, 2014 at 7:17
13

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).

3
  • Well done! This will only work in combination with the one in the Q though.
    – Graeme
    Feb 22, 2014 at 18:08
  • 1
    I believe you can simplify the first one if your regex engine allows variable-length negative lookahead: (.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!\4). Feb 23, 2014 at 15:07
  • @ChristopherCreutzig : Absolutely, nice call. I've add that in.
    – goldilocks
    Feb 24, 2014 at 16:24
6

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.

1
  • Thank you, but I'd like it as a regex oneliner :) Feb 22, 2014 at 16:54
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. :-)

1
  • I had to upvote this because it's actually an answer that would work. Though it might actually be the least efficient way anyone has written regex ever :P Feb 23, 2014 at 14:04
4

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.

2
  • Performance will depend a lot on the nature of the data. When doing tests on mine, I found that using non-greedy operators (\w{,8}?) helped for some type of input (though not very significantly). Nice use of \g{-1} to work around the GNU grep bug. Feb 24, 2014 at 11:46
  • @StephaneChazelas: Thanks for the feedback. I had also tried non-greedy and possessive operators and have not found a significant change in the run-time behavior (version 2.13). Version 2.18 is much faster and I could see at least a tiny bit of improvement. The GNU grep bug is present in both versions. Anyway I prefer the relative reference \g{-1}, because it makes the pattern more independent on the location. In this form it can be used as part of a larger pattern. Feb 24, 2014 at 20:30
0

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

6
  • The 1st and the 3rd does nothing, the 2nd outputs any line of 10 or more characters, with no more than 2 consecutive spaces. pastebin.com/eEDcy02D
    – manatwork
    Feb 22, 2014 at 19:45
  • it is probably the perl version. tested with v5.14.2 and v5.18.2
    – user55518
    Feb 22, 2014 at 20:26
  • I tried them with v5.14.1 on Linux and v5.14.2 on Cygwin. Both behaved like in the pastebin sample I linked earlier.
    – manatwork
    Feb 23, 2014 at 12:39
  • the first line works for me with the noted versions of perl. the two latter should work, because they are the same re, but didn't . perlre note often that some greedy expressions are highly experimental.
    – user55518
    Feb 23, 2014 at 12:47
  • Retested with your latest updates. Only the 2nd one outputs correctly. (However the word must be alone in a line, while the question is about matching words, not entire lines.)
    – manatwork
    Feb 23, 2014 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .