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:

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:

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, [ $-[0], $+[0]-$-[0] ], while $word =~ /oo/g;
  for my $p (@where) {
     my $other = $word;
     substr($other,$p->[0],$p->[1], "aa");
     push @words, $other if $other ne $word;

Leave a comment

About Alberto Simões

user-pic I blog about Perl. D'uh!