This should do it (the sub perm code has been shamelessly stolen from a StackOverflow answer, but I lost track of it):

   #!/usr/bin/env perl
    use strict;
    use warnings;

    my $tree = "(susie_ggo,(clint_ptr,(yri_hsa,chm13_hsa)),susie_pab);";
    my @tips = split( /[\(\),]+/, $tree);
    my $comma = pop @tips;
    my $space = shift @tips;
    (my $topology = $tree) =~ s/[a-z1-9_]+/PLACEHOLDER/gi;

    sub perm;
    foreach (perm \@tips) { 
      my $tmp = $topology;
      foreach my $tip (@$_) {
        $tmp =~ s/PLACEHOLDER/$tip/ ;
      }
      print "$tmp\n";
    }

    sub perm {
      my ($list) = @_;
      my $n = scalar @$list;
      return map [$_], @$list if $n <= 1;
      my @perm;
      for my $i (0 .. $#$list) {
        my @rest = @$list;
        my $val  = splice @rest, $i, 1;
        push @perm, [$val, @$_] for perm \@rest, $n-1;
      }
      return @perm;
    }