Match the permutations!

Question

Your challenge is to create a regex that matches every string permutation of itself, and nothing else. The match must also be case-sensitive.

So, for example, if your regex is:

ABC

It should match (and only match) these strings:

ABC
ACB
BAC
BCA
CAB
CBA

It shouldn't match things like:

AABC (contains an extra A)
ABCD (contains an extra D)
AC   (no B)
AAA  (no B and C, extra 2 A's)
abc  (case-sensitive)

Rules:

• You are allowed to use any flavour of regex you like.
• Standard loopholes apply.
• You must have at least two different characters in your code. That means solutions like 1 are invalid.
• The regex should contain only printable ASCII, and nothing else.

Answer 1

JavaScript, 64 57 bytes

4 bytes removed thanks to Martin Ender.

^(?!.*([^])(.*\1){3}]?)[$$[-^?!!.'''-*11{33}5577\\-]{57}$

Try it here.

Explanations (outdated)

^                                  # Beginning of the string.
(?!.*                              # Match only the strings that don't contain...
  (.)(.*\1){4}                     #     5 occurrences of the same character.
  [^1]?[^1]?                       #     Something that doesn't matter.
)
[]zzz^(?!!!.**[)\\1{{44}}666]{64}  # 64 occurrences of these 16 characters.
                                   # Some are duplicated to make sure the regex
                                   # contains 4 occurrences of each character.
\z                                 # End of the string.

Answer 2

JavaScript, 50 bytes

^(?!([^])+.*\1.*\1)[?!ZZ-__==''-22+,,//{50}$]{50}$

Try it on regex101

The key to beating jimmy23013's solution was to reduce the number of repetitions of each character from 3 to 2.

Explanation

^(?!([^])+.*\1.*\1) - assert that no character in the string is repeated at least 3 times

([^])+ is equivalent to .*([^]).

[^] works because JavaScript allows empty character classes (unlike most other regex engines, at least by default). It is equivalent to [\W\w] or . with the /s flag, i.e. it matches any character including newlines. For our purposes here, newlines don't matter, so it's equivalent to ..

Using ^(?!([^])+.*\1.*\1) instead of (?!.*([^])(.*\1){2}) or ^(?!(.)+.*\1.*\1) eliminates the need for a third (, ), or ., and this is the key to reducing the number of repetitions of every character from 3 to 2.

^...[?!ZZ-__==''-22+,,//{50}$]{50}$ - assert that the entire string consists of the 25 characters ? ! Z [ \ ] ^ _ = ' ( ) * + , - . / 0 1 2 { 5 } $ and is 50 characters in length. Combined with the first assertion this guarantees that every character occurs exactly twice (due to the generalized pigeonhole principle, if any character occurred only once, some other character would have to occur three times).

Z-_ is the range Z[\]^_. It's essential, because we already used [, \, ], and ^ twice each. We need to double the Z and _, because they aren't used elsewhere.

'-2 is the range '()*+,-./012. It's essential, because we already used (, ), *, ., and 1 twice each. We need to double the ', ,, /, and 2, because they aren't used elsewhere.

There is no other way besides ranges to include the above in our character class, because octal or hexadecimal escape codes would require using \, and a negative character class would require using ^.

== is extra padding to get us to 50 characters. It could be any arbitrary doubled character. We need it because if we went for {48}, we'd need to include two 0 somewhere, which would bring our 48 back up to 50.

Note that this can be trivially rearranged to include the delimiters:

/^(?!([^])+.*\1.*\1)[?!ZZ-__==''-22+,,{50}$]{50}$/

Try it on regex101

Perl / PCRE, 57 bytes

I'm pretty sure it's impossible to do 2 repetitions in Perl/PCRE, because [^] is not available (except with the PCRE2_ALLOW_EMPTY_CLASS flag), and the only other alternatives use \ – for example \C, \N, \X, \S, and [^\0]. So, with 3 repetitions:

^(?!(.)*(.*\1){3})[[[-\]\]^^??!!'''-*.11{335577}$$-]{57}$

Try it on regex101

This is very similar to jimmy23013's JavaScript solution. It doesn't work under JavaScript however, because ^(?!(.)*(.*\1){3}) can always match on any string; it would capture an unset \1 by doing zero repetitions on (.)*, and then \1 would match an empty string 3 times.

Making it portable to both JavaScript and Perl/PCRE by using (.)+ instead of (.)* would end up making it 60 bytes, due to adding the + character.

Alternatively:

((.)+(.*\2){3})?+^[[[-\]\]^^??+'''-**.22{335577}$$-]{57}$

Try it on regex101

This uses the possessive quantifier ?+ to atomically try to match a character repeated 4 times. If such a match is not found, it will be forced to do zero repeats (instead of one) and the ^ will match. Otherwise it will match something non-empty, and the ^ won't match.

Answer 3

Perl and PCRE regex, 280 bytes

^(?=(.*z){2})(?=(.*\(){43})(?=(.*\)){43})(?=(.*\*){22})(?=(.*\.){23})(?=(.*0){2})(?=(.*1){6})(?=(.*2){16})(?=(.*3){7})(?=(.*4){4})(?=(.*5){1})(?=(.*6){3})(?=(.*7){2})(?=(.*8){2})(?=(.*9){1})(?=(.*=){22})(?=(.*\?){22})(?=(.*\\){11})(?=(.*\^){2})(?=(.*\{){23})(?=(.*\}){23}).{280}\z

(Slightly) more readable:

^
(?=(.*z){2})
(?=(.*\(){43})
(?=(.*\)){43})
(?=(.*\*){22})
(?=(.*\.){23})
(?=(.*0){2})
(?=(.*1){6})
(?=(.*2){16})
(?=(.*3){7})
(?=(.*4){4})
(?=(.*5){1})
(?=(.*6){3})
(?=(.*7){2})
(?=(.*8){2})
(?=(.*9){1})
(?=(.*=){22})
(?=(.*\?){22})
(?=(.*\\){11})
(?=(.*\^){2})
(?=(.*\{){23})
(?=(.*\}){23})
.{280}\z

This runs in O(2^n) time as written, so is incredibly inefficient. The easiest way to test it is to replace every occurrence of .* with .*?, which causes the case where it matches to be checked first (meaning that it matches in linear time, but still takes exponential time if it fails to match).

The basic idea is that we enforce the length of the regex to equal 280, and use lookahead assertions to force each character in the regex to appear at least a certain number of times, e.g. (?=(.*z){2}) forces the z character to appear at least twice. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23 is 280, so we can't have any "extra" occurrences of any characters.

This is a programming example of an autogram, a sentence that describes itself by listing the number of each character it contains (and, in this case, also the total length). I got fairly lucky in constructing it (normally you have to use brute force but I stumbled across this solution while testing my brute-force program before I'd fully finished writing it).

Perl and PCRE regex, 253 bytes, in collaboration with Martin Ender

I hypothesized that there might be shorter solutions which omit some digits (most likely 9, 8, or 7). Martin Ender found one, shown below:

^(?=(.*z){2})(?=(.*\(){39})(?=(.*\)){39})(?=(.*\*){20})(?=(.*\.){21})(?=(.*0){4})(?=(.*1){6})(?=(.*2){11})(?=(.*3){6})(?=(.*4){3})(?=(.*5){2})(?=(.*6){3})(?=(.*9){4})(?=(.*=){20})(?=(.*\?){20})(?=(.*\\){9})(?=(.*\^){2})(?=(.*{){21})(?=(.*}){21}).{253}\z

Readable version:

^
(?=(.*z){2})
(?=(.*\(){39})
(?=(.*\)){39})
(?=(.*\*){20})
(?=(.*\.){21})
(?=(.*0){4})
(?=(.*1){6})
(?=(.*2){11})
(?=(.*3){6})
(?=(.*4){3})
(?=(.*5){2})
(?=(.*6){3})
(?=(.*9){4})
(?=(.*=){20})
(?=(.*\?){20})
(?=(.*\\){9})
(?=(.*\^){2})
(?=(.*{){21})
(?=(.*}){21})
.{253}\z