Perhaps the following will be helpful:

use strict;
use warnings;

my $chars = 'ABC---';

my %seen;
my @letters = grep /[a-z]/i, split '', $chars;
my $regex = join '.*', @letters;
my $string = ( '{' . ( join ',', split '', $chars ) . '}' ) x length $
+chars;

print "$_\n"
  for grep { /$regex/ and !$seen{$_}++ and @{ [/[a-z]/ig] } == @letter
+s }
  glob $string;
[download]

Output:

ABC---
AB-C--
AB--C-
AB---C
A-BC--
A-B-C-
A-B--C
A--BC-
A--B-C
A---BC
-ABC--
-AB-C-
-AB--C
-A-BC-
-A-B-C
-A--BC
--ABC-
--AB-C
--A-BC
---ABC
[download]

This 'brute force' approach uses glob to generate all possible combinations of the characters. Each combination is grepped for the order of characters (/$regex/), whether it's already been seen (!$seen{$_}++) and for the correct number of letters (@{ [/[a-z]/ig] } == @letters).