A solution using Algorithm::Combinatorics.

#!/usr/bin/perl
use strict;
use warnings;
use Algorithm::Combinatorics qw/combinations/;

my $input  = 'ABC---';

my $dashes = $input =~ tr/-//;
my @letters = $input =~ /[A-Z]/g;

my @positions = 0 .. ($dashes + @letters)-1;
my @idx = combinations(\@positions, scalar @letters);

for my $indices (@idx) {
    my @comb = ('-') x ($dashes + @letters);
    @comb[@$indices] = @letters;
    print @comb, "\n";
}
[download]