Generating all permutations from a regexp

[Chris Johnson]

BJörn Lindqvist wrote:
> With regexps you can search for strings matching it. For example,
> given the regexp: "foobar\d\d\d". "foobar123" would match. I want to
> do the reverse, from a regexp generate all strings that could match
> it.
>
> The regexp: "[A-Z]{3}\d{3}" should generate the strings "AAA000",
> "AAA001", "AAA002" ... "AAB000", "AAB001" ... "ZZZ999".
>
> Is this possible to do? Obviously, for some regexps the set of matches
> is unbounded (a list of everything that matches "*" would be very
> unpractical), but how would you do it for simple regexps like the one
> above?

For a very small number of characters, it would be feasible. For any
finite number of characters, it would be possible (though it wouldn't
take much to take longer than the age of the universe). For reference,
in your simple example, you have 17,576,000 matching strings.

I'm curious as to why you would wish to do this. I certainly understand
considering hard problems for their own sake, but when I formulate
them, there's always some impetus that makes me say "Huh. Now I
wonder..."