def vary(target, pattern, subst):
    numOccurences = len(pattern.findall(target))
for path in itertools.product((True, False), repeat=numOccurences):
    variant = ''
remainingStr = target
for currentFlag in path:
    if currentFlag:
        remainingStr = pattern.sub(subst, remainingStr, 1)
else:
    currentMatch = pattern.search(remainingStr)
variant += remainingStr[:currentMatch.end()]
remainingStr = remainingStr[currentMatch.end():]
variant += remainingStr
yield variant
Combinatorial product of regex substitutions