Pattern Matching Exclude Duplicate Characters

Question

Is there a regular expression for the following that matches characters in a character set but only once? In other words, once a character is found, remove it from the set.

If grep cannot do this, is there a built-in utility which can?

Example:

Characters to match only once:   spine

Input:

spine
spines
spin
pine
seep 
spins

Output:

spine
spin
pine

EDIT:
There are many ways to achieve this output (one example below), but I'm looking for a way to do this without having to customize the command for each pattern I want to match.

grep '[spine]' input_file | grep -v 's.*s' | ... | grep -v 'e.*e'

Answer 1

With regular expressions in the mathematical sense, it's possible, but the size of the regular expressions grows exponentially relative to the size of the alphabet, so it isn't practical.

There's a simple way with negation and backreferences.

grep '[spine]' | grep -Ev '([spine]).*\1'

The first grep selects lines that contain at least one of einps; the second grep rejects lines that contain more than one of any (e.g. allowing spinal tap and spend but not foobar or see).

Answer 2

Inspired by your expression, I can come up with a shorter one, using egrep:

egrep -v '(s.*s|p.*p|i.*i|n.*n|e.*e)' FILE

which is equivalent to

sed /s.*s/d;/p.*p/d;/i.*i/d;/n.*n/d;/e.*e/d; FILE

And this is how to produce the sed-command from the input automatically:

#!/bin/bash
word=$1
file=$2
expr=$(for c in $(echo $word | sed 's/./& /g'); do echo -n "/"$c".*"$c"/d;"; done);
sed $expr $file 

I tried a similar approach with grep, but couldn't convince the shell to take the grep-pattern from a variable, but if I echoed it out, and inserted the result with cut and paste, the command worked:

expr="'("$(for c in $(echo $wort | sed 's/./& /g'); do echo -n $c".*"$c"|"; done)

egrep -v ${expr/%|/)\'} FILE
# doesn't work, filters nothing, whole file is printed
# check:    
echo egrep -v $(echo $exp) FILE 
egrep -v '(s.*s|p.*p|i.*i|n.*n|e.*e)' FILE
# manually: 
egrep -v '(s.*s|p.*p|i.*i|n.*n|e.*e)' FILE
spine
spin
pine

Maybe I made an error, maybe I make a mistake with variable expansion.