Alberto Simões

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, [ $-[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;
  }