AM gave you a valuable hint about shuffling and I second mbethke's suggestion on rather testing the user provided password with an appropriate password checker.

Despite the security issues, here's a hint to you Perl problem using your original code with some annotations and corrections:

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

my @chars   =   ( "a" .. "k", "m","n", "p" .. "z");
my @upchars =   ("A".."N","P".."Z");   # <-- NOTE: "P..Z" -> "P".."Z"
my @nona    = qw(! @ $ % & ( ) + = { } [ ] < > ~);
my @nums    =   (0 .. 9);

my $lc = \@chars;
my $uc = \@upchars;
my $na = \@nona;
my $nu = \@nums;

my @types = ($lc, $uc, $na, $nu);      # compact: my @types = (\@chars
+, \@upchars, ...

my $a  = join("", @{$types[3]}[ map { rand @{$types[3]} } ( 1 .. 4 ) ]
+);
   $a .= join("", @{$types[2]}[ map { rand @{$types[2]} } ( 1 .. 4 ) ]
+);
   $a .= join("", @{$types[1]}[ map { rand @{$types[1]} } ( 1 .. 4 ) ]
+);
   $a .= join("", @{$types[0]}[ map { rand @{$types[0]} } ( 1 .. 4 ) ]
+);
#                  ^--deref/arrayslice      ^-- deref for number of el
+ements

# nobody complained about using '$a' yet, so I don't do either ;-)

print "My selection is $a \n";
# you should shuffle and shorten the result

exit;

__DATA__
My selection is 0548)~}+QRVKzkkt
My selection is 7922&)(&AAZZwiaw
My selection is 5263+!@>VXXBaezt
[download]

Enforcing someone to use e.g. 0548)~}+QRVKzkkt as a password just increases post-it sales... ;-)

You need to work with lists

Choose-N from each set

my @chosen = ChooseN( 2 , \@set );
push @chosen, ChooseN( 4 , \@set );
push @chosen, ChooseN( 6 , \@set );
push @chosen, ChooseN( 8 , \@set );
[download]

Then shuffle those playing cards :)

use List::Util 'shuffle';
@chosen = shuffle @chosen;
[download]

And then make them presentable

my $chosen = '';
while(@chosen){
   $chosen .= join '', splice @chosen, 0, 6;
   $chosen .= ' ' if @chosen;
}
return $chosen;
[download]

What am I doing wrong and am I even on the right track?

Not sure, but see also Opportunity to excel / Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes

And see also Crypt::RandPasswd, Crypt::PassGen, String::MkPasswd

Hi desertrat,
before I spend time on working out how to do it, I'd rather spend a few minutes persuading you that it's not a good idea. I know, oftentimes it's come corporate-level decision that you just have to implement, but if you have any say in it: don't. It's fine to require some classes of characters to keep people from using all too simple variations of distionary words, but

1. four is excessive, i.e. it already limits the number of allowable passwords too much, and
2. imposing rules on supposedly "random" distribution limits them even more, making brute-force cracking actually easier.

Sadly it's a corporate-level decision being made by an entirely different corporation (We have a group contracted to do work for outside companies), so I have to do it this way. I know this is a PITA and just results in passwords being taped to the front of monitors, let alone under the keyboards, but a code monkey's gotta do what a code monkey's gotta do sometimes.

Had I any say I would offer Randall Munroe's excellent treatise on the matter as the help file.

Silly idea but, as you say, the decision is out of you hands :-(

Set up the four sets already shuffled then make an array of references to them. Then create another array with a guaranteed one from each set (0 .. 3) then a random selection of four more from any set. Then shuffle the order. Finally, build the password by concatenating random letters from the sets in the already shuffled order.

knoppix@Microknoppix:~$ perl -MList::Util=shuffle -Mstrict -wE '
my @lc  = shuffle q{a} .. q{z};
my @uc  = shuffle q{A} .. q{Z};
my @dig = shuffle q{0} .. q{9};
my @oth = shuffle qw{ ! " £ $ % ^ & * _ - + = @ ~ };
my @all = \ ( @lc, @uc, @dig, @oth );

my @order = ( 0 .. 3 );
push @order, int rand 4 for 1 .. 4;
@order = shuffle @order;

my $passwd = q{};
$passwd .= $all[ $_ ]->[ rand @{ $all[ $_ ] } ] for @order;

say $passwd;'
E5yR=$%£
knoppix@Microknoppix:~$
[download]

Runs of this have produced &D0%@nn%, F9@F=Rc1, S~j@3WgG, 633P£m!T and o8S4pl!! so, as long as there is no stipulation barring repeated characters, this seems to work.

I hope this is useful.

Update: If repeated characters are not wanted then you can use splice to remove the chosen character from the array so it can't be re-used.

...
$passwd .= splice @{ $all[ $_ ] }, rand @{ $all[ $_ ] }, 1
   for @order;
...
[download]

I think I see the way now, thank you to all for your help. I realize now that I completely neglected to mention that this was not the intended end function, but a test just to make sure I was getting some of all of them!