One line, using a substitution wrapped in a while loop and no split. Obviously, you can remove the print statements with no ill effect. A split-base solution as offered by Yary and ikegami is probably clearer and more maintainable. This algorithm assumes you can easily differentiate your keys from your values, as in your example.

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

my $n_terms = 5;
my $string = "";
my $letter = "A";
$string .= $letter++ . " # " for (1 .. $n_terms);
$string .= join " # ", 1 .. $n_terms;

print "Input:        $string\n";

while ($string =~ s/((?:^|[0-9]+\s*\#\s*)[A-Z]+\s*\#\s*)
                    ([^0-9]+?\#\s*)
                    ([0-9]+\s*\#\s*)
                    /$1$3$2/x) {
    print "Intermediate: $string\n";
};

print "Output:       $string\n";
__END__
Input:        A # B # C # D # E # 1 # 2 # 3 # 4 # 5
Intermediate: A # 1 # B # C # D # E # 2 # 3 # 4 # 5
Intermediate: A # 1 # B # 2 # C # D # E # 3 # 4 # 5
Intermediate: A # 1 # B # 2 # C # 3 # D # E # 4 # 5
Intermediate: A # 1 # B # 2 # C # 3 # D # 4 # E # 5
Output:       A # 1 # B # 2 # C # 3 # D # 4 # E # 5
[download]