#!/usr/bin/perl
use Algorithm::Loops qw/NextPermute/;


my $input = 'AMGK-MVSPAMK';
my $n = 1;
my $M = 'M';
my $X = 'X';

my @sections = split(/$M/, $input);

my $size = @sections;

my @replacements = sort split(//,  ($X x $n) . ($M x ($size - $n - 1)));

do {
  my @b = (@replacements, '');
  print join("", map { $sections[$_] . $b[$_] } (0..$#sections) ). "\n";
} while (NextPermute(@replacements));