Determining the number of possible combinations

Question

I'm trying to figure out how many possible ways there are to combine various elements form this string.

"{Hello|Hi|Hey} {world|earth}{!|.|?}"

Where one item (separated by a pipe/|) is selected at random from each group ({}) and combined into a single string.

So the above "template" could produce:

Hello world.
Hi earth?
Hey world.
Hi world?

I'm guessing this is a type of permutation, but I want to make sure I'm getting this right.

It would be really nice if this worked with "n" nested items as well.

"{{Hello|Hi|Hey} {world|earth}|{Goodbye|farewell} {noobs|n3wbz|n00blets}}"

I'd prefer a math/statistics based solution over brute-force looping to get the answer if possible.

Thanks!

Answer 1

The problem breaks down to two simple sub-problems:

1. count how many combinations are within braces and separated within vbars, for each braces pair
2. multiply those numbers

So for 1 I'd go with a plain regular expression + looping approach:

import re

def docount(thestring):
    x = re.compile(r'{([^}]}')
    counts = [mo.group(0).count('|')+1 for mo in x.finditer(thestring)]
    result = 1
    for c in counts: result *= c
    return result

I've embedded 2 as well since that's the most trivial part anyway (if you're keen on using reduce for such purposes, that's OK too in lieu of the last three lines, I guess;-).