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

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