Re: [SPOILER] Solution for QOTW 23

Mark Jason Dominus:
> #!/usr/bin/perl -l
> 
> print $_ = "()" x shift;
> print while s{^  ( \(+ )  ( \)+ ) \(  }
>              {"()" x (length($2) - 1)
>               . "("  x (length($1) - length($2) + 2) 
>               . ")" 
>              }xe;
> 

So, YST said he couldn't picture an algorithm that would produce the
strings in lexicographic order.    This one doesn't, quite:

        ()()()()
        (())()()
        ()(())()
        (()())()
        ((()))()
        ()()(())
        (())(())
        ()(()())
        (()()())
        ((())())
        ()((()))
        (()(()))
        ((()()))
        (((())))

But that's only because I have it working from the front end instead
of he back end.   My previous version started at the back of the
string and did produce the output in sorted order; I changed it around
because it's much cheaper to do the regex matches at the front rather
than the back.  

So to get the lexicographic order, either reverse the algorithm, like this:

> print while s{  \) ( \(+ )  ( \)+ ) $  }
>              {"(" 
>               . ")"  x (length($2) - length($1) + 2) 
>               . "()" x (length($1) - 1)
>              }xe;

or else just pipe the output through

     perl -lpe '$_ = reverse; tr[()][)(]'

and there you go, lexicographic order:

        ()()()()
        ()()(())
        ()(())()
        ()(()())
        ()((()))
        (())()()
        (())(())
        (()())()
        (()()())
        (()(()))
        ((()))()
        ((())())
        ((()()))
        (((())))

Have I mentioned how delighted I am with this solution?  I originally
planned to do a recursive thing like many of the others that were
posted, but then I discovered this instead.