Generating minimal regular expression character classes

Question

Background

Character classes are a standard way to indicate a set of characters to match in regular expressions. For example, the class [ab] matches a or b, [a-z] matches any lower case letter, and [^a] matches everything but a. For the purpose of this question, classes can contain:

• a sequence of characters to match, where the characters \, ], - and ^ must normally be escaped with a \.
• a range of characters to match, indicated by separating two characters with a -: e.g. [0-9]. Note that if - is the first or last character in a class then it need not be escaped, as it's not indicating a range.
• a combination of sequences and ranges: e.g. [ac-fhk-o]. Note that the class cannot be empty, and if ] is the first character in the class then it need not be escaped.
• a complement match indicated by the first character in the class being ^: e.g. [^a-z]. Note that if ^ is not the first character in the class, then it need not be escaped.

Task

Given a non-empty string made up of printable ASCII characters (" " to "~" = 0x20-0x7E), output the shortest character class that matches precisely those characters. The string may contain duplicate characters. Default Input/Output methods apply.

Scoring

This is code-golf, so shortest code in bytes wins, with all the standard loopholes forbidden.

Test cases

"the"     => "[the]" or "[eht]" etc
"faced"   => "[ac-f]" or "[c-fa]"
"0-121"   => "[-0-2]" or "[012-]" etc
"]"       => "[]]"
"[-^]"    => "[][^-]" or "[]^[-]"
"[\]"     => "[[-\]]" or "[]\\[]" or "[][\\]"

Answer 1

No answers after a few days, so thought I'd have a go. Found it trickier than expected, so the answer's pretty long, but I'm reasonably confident it works. Should be able to trim it a fair bit more.

Python 3.8, 431 405 410 bytes

import re,itertools as I
B,M,C,P="\-]^"
s=sorted;x=s({*input()})
d=[ord(x)-i for i,x in enumerate(x)];l=[];i=0
for _,g in I.groupby(d):n=len([*g]);l+=[[x[i]+M+x[i+n-1]],x[i:i+n]][n<4];i+=n
o="".join(s(l,key=lambda i:2*(M in i[::2])+(P in i)-3*(i[0]==M<C not in x)-2*(C in i)))
print("["+re.sub(".",lambda m:B*((x:=m.group())==B or x==P==o[0]or x==M<M*2==o[(i:=m.start()):i+2]in o[1:-1]or x==C in o[1:])+x,o)+C)

Try it online!

Explanation

The overall approach is to:

1. Split the letters into ranges of length at least 4 and individual characters. Note that ranges of length 3 are never necessary (eg. "[abc]" is the same length as "[a-c]" and "[]\\[]" is the same length "[[-\]]") and are sometimes worse (e.g. "]-./" is shorter as "[]./-]" than as "[]\--/]" or "[--/\]]").

2. Sort the letters and ranges, so "]" goes first, otherwise "-" goes first, otherwise "-" goes last, and with "^" as late as posssible. There is no conflict between putting "]" first and "-" last since "]--" is not a valid range.

3. Escape as necessary: \ always, ] unless it's first, ^ if it's first, and - if it's in the middle (which will only happen if it's the beginning of a range).

Extra test cases

"-^"      => "[-^]"
"-4]"     => "[]4-]"
"abcde^"  => "[a-e^]"
"XYZ[\\]" => "[X-\]]"
"-./0]"   => "[]\--0]"
"+*,-^"   => "[\^*--]"
"^_`a"    => "[\^-a]"