Regex to check non-repetition of a set of characte

Question

Suppose I have the set of characters [ABC]. I'm looking for a regex that would match any permutation of the superset except the empty set, i.e.

ABC ACB BAC BCA CAB CBA
AB BC AC CB CA BA
A B C

The regex should (obviously) not match the empty string.

p.s. An alternative way to express the same objective is "match any non-empty string containing each character in the set at most once".

update: The set [ABC] is just an example, for the real set may also be bigger. With this question I was hoping to find a "general" solution rather than a particular one for [ABC].

Answer 1

Try this : (UPDATED)

A[BC](?![ABC])|B[AC](?![ABC])|C[AB](?![ABC])|[ABC](?![ABC])|(ABC|ACB|BAC|BCA|CAB|CBA)(?![ABC])

Demo :

http://regexr.com?30pa6

Answer 2

This is not something that regular expressions are good at. You might just want to create a list of permutations instead, and then produce all unique substrings.

something like:

def matches(s, characters):
    if len(s) != len(set(s)):
        return False # not unique sequence of characters
    return set(s).issubsetof(set(characters))

Answer 3

Here's my version:

\b(?=[ABC]{1,3})([ABC]{1})(?:(?!\1)([ABC]{1})(?:(?!\1)(?!\2)[ABC]{1})?)?\b

Logic:

• \b: look for a word boundary
• (?=[ABC]{1,3}): lookahead to see if there is a string of length = 3 with values of only A, B, C
• ([ABC]{1}): match the first character then optionally
• (?!\1)([ABC]{1}): check if the next character is not the same as previously matched - if it's not, match it and optionally
• (?!\1)(?!\2)[ABC]{1}: check if the next character is not the same as previously matched char 1 or 2 - if it's not, match the character

I tested it against this input, so it seems quite reliable:

AABCC BBCC AB BC AC CB CA BA A B C ABC ACB BAC BCA CAB CBA AAA ABB AAA BBC AA

---

EDIT:

As you mentioned the character set can be larger I would follow the PS advice in your question and do this the following way:

• introduce chars array which will hold each character in the allowed set (split the string into chars)

• get an array of inputStrings (split the input string on whitespace or whatever else required)

• for each string in inputStrings {

• check if the string.length <= inputStrings.length
• tryMatch each character in the list against the current input and save the number of matches found in a matches list
• check if the matches list contains any entries and then if all entries == 1 or 0 }

Answer 4

"A((B?C?)|(C?B?))|B((A?C?)|(C?A?))|C((A?B?)|(B?A?))"

It is A|B|C and each of them can be followed by an pair of optional values

 A(B?C?) matches A, AB,AC and ABC
 A(C?B?) matches A, AC,AB and ACB 

but not ACAC, AA or ACC. The cases with B or C as first character are equivalent.

For longer Strings, this will get ugly soon. A better approach would be (pseudocode):

 string.sort().matches ("^A?B?C?$") && string.length > 0

Answer 5

Thanks to your answers (especially anubhava's and codaddict's) I was able to find this solution, that I think is pretty elegant because it allows to type the set only once:

\b(([ABC])(?!.*\2))+\b

the \b are needed to match full words; omitting them will also find subwords respecting the required property. To match a full string, you'd obviously do:

^(([ABC])(?!.*\2))+$

Answer 6

I believe this can be solved by regular expressions. Use this regex:

/^([ABC])(?!\1)([ABC])?(?!\1|\2)[ABC]?$/

Let me know if you need an online demo on this.