Your solution, and the solutions offered so far, all appear to generate an array with the proposed results. This is okay, but will chew up memory the longer the string of bases. *

What you really want is a lazy iterator that will fetch the next sequence in the solution space. The following does what you want, at a greatly reduced cost in memory

#! /usr/local/bin/perl -w

use strict;


my @nuc = qw/ A T C G /;

sub inc {
        $_[0] eq 'A' and return 'T';
        $_[0] eq 'T' and return 'C';
        return 'G';
}

sub gen {
    my @current = @_;
    my $done = 0;
    return sub {
         return if $done;
         my @res = @current;
         my $i;
         ITER: for ($i = 0; $i < scalar @current; ++$i) {
             if( $current[$i] ne $nuc[-1] ) {
                 $current[$i] = inc($current[$i]);
                 last;
             }
             else {
                 $current[$i] = $nuc[0];
             }
         }
         $done = 1 if $i >= scalar @res;
         return @res;
    }
}

my @set = ('A') x (shift || 3);
my $iter = gen( @set );

while( my @iter = $iter->() ) {
    print "@iter\n";
}
[download]

The inc kluge to move to the next base is a bit too ugly, there are better ways of doing this, but I leave that as an exercise to the reader.

If you are interested in learning more about iterators, I draw your attention to Dominus' forthcoming book, Higher Order Perl.

---

* I thought gaal's for 0 .. n constructed a list. It used to be the case on old perls, but gaal assures me this hasn't been the case in years. Which just goes to show that you learn something every day.