## Combinatory Substitution

Not sure if the title is understandable. But I will give an example. Consider a word (well, invented one): noogoo. Now, consider you want to do all possible combinations substituting oo with aa, that is, generate naagoo and noogaa.

The solution I am using, that was idea of my friend Luciano, is as follows:

``````    \$word = "noogoo";
push @where, pos(\$word)-2 while \$word =~ /oo/g;
for my \$i (@where) {
my \$other = \$word;
substr(\$other,\$i, 2, "aa");
push @words, \$o if \$o ne \$word;
}
``````

Any better or more efficient idea?

This module uses knuth's combinatorial methods which allow iterations with minimal remembering:
http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.25/Combinatorics.pm

Is it intentional that "naagaa" isn't a listed combination?

I like the question and came up with a recursive solution. The code is posted here: http://gugod.org/2010/07/post-79.html

It probably dose not meet your original requirement but it's fun thinking the solution. Thanks for the question :)

it is like counting in base two:

```my \$word = 'raataacaataacaataamooonpaapaa';

my \$zero = 'aa';
my \$one  = 'ooo';

my \$qzero = quotemeta \$zero;

my @frag = split /(\$qzero)/, \$word;
my @ix = grep \$frag[\$_] eq \$zero, 0..\$#frag;

sub forward {
for my \$ix (@ix) {
if (\$frag[\$ix] eq \$zero) {
\$frag[\$ix] = \$one;
return 1;
}
\$frag[\$ix] = \$zero;
}
return 0;
}

print join('', @frag), "\n" while forward;
```

Rather than presume a constant length match length, and hardcode that 2 twice, consider:

```  \$word = "noogoo";
push @where, [ \$-, \$+-\$- ], while \$word =~ /oo/g;
for my \$p (@where) {
my \$other = \$word;
substr(\$other,\$p->,\$p->, "aa");
push @words, \$other if \$other ne \$word;
}``` I blog about Perl. D'uh!