Regex to check non-repetition of a set of characters

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

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.

Answer 2

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 3

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 4

Try:

([ABC]?)(?!.*\1)([ABC]?)(?!.*\2)[ABC]?

It is just [ABC]? repeated 3 times with the added check of the negative lookahead assertion that does not permit duplicate characters.

Note that this would work only if the input set is all unique.

See it work

Answer 5

"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 6

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 7

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 8

OK, I must say that I've thought about your question a lot and - since you seem to be wanting something really universal and customiseable (to support as many elements as possible, etc) - this is what I think would make the most optimal solution.

What you want, from a math perspective, is to identify all permutations of a set of elements without repetition.

---

Step 1 :

Find all permutations of the set, with repetition (and store them let's say in an array)

[ABC]([ABC]{1,2})?

Sidenote : let's say you have a set with n elements, all you have to do is :

[elements]([elements]{1,n-1})?

---

Step 2 :

Filter all permutations with duplicate elements

Example code in PHP :

<?php

    function strToArray($str)
    {
        $i = 0;

        while (isset($str[$i]))
        {
            $result[$i] = $str[$i];
            $i++;
        }

        return $result;
    }

    function noDuplicates($str)
    {
        if (array_unique(strToArray($str))==strToArray($str)) return true;
        else return false;
    }

    $AAA = "AAA";
    $ABC = "ABC";

    if (noDuplicates($AAA)) echo "$AAA : ok"; else echo "$AAA : not ok\n";
    if (noDuplicates($ABC)) echo "$ABC : ok"; else echo "$ABC : not ok\n";

?>

Output :

AAA : not ok
ABC : ok