Here is some code that works very well for me.

#! /usr/bin/perl -w

use strict;

my @array = @ARGV ? @ARGV : qw/mix up these words in new ways/;

sub fac {
   my $nr = shift;
   return 1 if $nr < 2;
   return $nr*fac($nr-1);
}

my %seen;
my $max = fac(scalar @array);
my $nr  = 0;
while( $nr < $max ) {
    my $need_combo = 1;
    my @combo;
    while( $need_combo ) {
        for( my $i = 0; $i < scalar @array; ++$i ) {
            $combo[$i] = $array[ rand scalar @array ];
        }
        my %unique;
        my $unique = 1;
        for my $c ( @combo ) {
            if( ++$unique{$c} > 1 ) {
                $unique = 0;
            }
        }
        if( $unique == 1 ) {
            $need_combo = 0;
        }
    }

    if( exists $seen{ "@combo" } ) {
        next;
    }
    else {
        local $" = "\t";
        print "@combo\n";
    }
    ++$seen{"@combo"};
    ++$nr;
}
[download]

There are possibly some minor performance tweaks that could be added, but I have chosen clarity over performance. Hope this helps.

Oops, I just re-read your question. You said you wanted combinations of this array, but apparently you also want selections. Oh well, I'm sure you can figure out easily enough how to extend this program to get it to do that too.