Yes, the clever curly-bracket notation from csh -- forms
the cartesian product.
Also works if they're *nested*.
Now this, for John, Abigail, MJD, etc:
"YOUR TASK, MR. PHELPS, IS TO PROGRAM THAT CSH ALGORITHM"
How about an efficient algorithm on doing that?
Funny you should mention that, because I was using that as a basic
example of a 'Cartesian product' in chapter VII of my book
(
http://perl.plover.com/book/chap07.html) so I was planning to write
that anyway. In fact, I thought I had written it already, but if I
did I can't find it. I think the delay was occasioned by the fact
that I thought of two or three different ways to do it, but I wasn't
sure which one I liked best.
I do have analogous code which takes a regular expression and
generates a list of all the strings that will match the regex. This
includes your problem as a sub-case, because the regex might be
/^(A|B)(C|D)XY$/
which is equivalent to the "{A,B}{C,D}XY" example you have above, only
with different notation.
Note that when each pair of curly braces contains only a finite number
of alternatives, the problem is quite easy, because you can generate
the result with what is esentially a set of nested 'for' loops. For
example, when the expression to expand is
foo{x,y,z}{1,2,3}.txt
you want to execute some code that is equivalent to
for $a ('x', 'y', 'z') {
for $b (1, 2, 3) {
# do something with "foo$a$b.txt"
}
}
The problem becomes much more interesting when when one or more of the
sets of alternatives mught be infinite. In that case the 'nested for
loop' approach no longer works. Suppose the expression to expand is
foo{a,b,c,...,z,aa,ab,ac,...}{1,2,3,...}.txt
Then the analogous 'for' loops are
for $a ('a', 'b', 'c', ..., 'z', 'aa', 'ab', ...) {
for $b (1, 2, 3, ...) {
# do something with "foo$a$b.txt"
}
}
but, because the inner loop is infinite, the program never gets to the
second iteration of the outer loop, and so only produces strings that
begin with "fooa". So you need a different (and more complicated)
strategy if any of the alternatives might contain infinite sets.
Anyway, the problem in the finite case is not that hard, and I am sure
you would be able to solve it if you put your mind to do it. I would
suggest that you first try to solve the problem for the case where the
string contains only one curly-brace expression. That will give you
code that takes a string and eliminates a single set of curly braces
from it, yielding a list of strings. Once you do that, it's easy to
deal with many sets of curly braces: just call your one-curly-brace
handler repeatedly to eliminate one set of curly braces after another.