If by parity you simply mean even or odd, I tried Algorithm::FastPermute.

#!/usr/bin/perl

use strict;
use warnings;
use Algorithm::FastPermute qw(permute);

my(@array) = (1, 2, 3,4);

my $i = 0;
permute { while (++$i){return} } @array ;
foreach my $number(@array) {
    if (($number % 2) == 0) {
        print "even\n";
    }
    else {
        print "odd\n";
    }
}
[download]

returns:
odd
even
odd
even
[download]