Oh monks of the round table, who dance whene'er they're able, who dine well here in Camelot and eat ham and jam and spam a lot!

Can someone recommend a faster alternative to Math::Combinatorics, or maybe suggest a better way of doing the following?

I'm trying to generate all multisets (bags) of a specific total "weight" (let's call it w), where each element comes from a given list (of numbers, in this case), and each list element may have multiplicity 0..w in each multiset. In other words, what I'm trying to generate is a list of w-tuples of elements of the given list — but unordered tuples rather than ordered ones.

An example may be instructive. Let's say w is 4, and the list is (0, 2, 3). Then I'd like to get the following multisets:

0,0,0,0
0,0,0,2
0,0,0,3
0,0,2,2
0,0,2,3
0,0,3,3
0,2,2,2
0,2,2,3
0,2,3,3
0,3,3,3
2,2,2,2
2,2,2,3
2,2,3,3
2,3,3,3
3,3,3,3
[download]

(The order in which the multisets itself are generated isn't important to me either, BTW. I've only listed them in order for the sake of readability.)

Not wanting to implement this myself, I turned to CPAN and found Math::Combinatorics. This works, but it's fairly slow. Here's a (slightly simplified) excerpt from my code:

#!/usr/bin/perl

use Modern::Perl '2015';
use Math::Combinatorics;

my $states = 4;

foreach my $count (1, 2, 3, 4, 7, 8) {

    say "count=$count";

    my $iter = Math::Combinatorics->new(
            count     => $count,
            data      => [ grep { $_ != 1 } (0 .. ($states - 1)) ],
            frequency => [($count) x ($states - 1)]
        );

    while(my @states = $iter->next_multiset) {
        say join(",", @states);
    }
}
[download]

This produces the desired output, but it takes almost 90 seconds to run for $states = 4, and much longer for 5 and up:

time perl test.pl
count=1
3
0
2
count=2
0,0
0,2
0,3
2,3
2,2
3,3
count=3
3,0,0
3,0,2
3,0,3
3,2,3
3,2,2
3,3,3
0,0,2
0,0,0
0,2,2
2,2,2
count=4
3,2,0,3
3,2,0,2
3,2,0,0
3,2,3,2
3,2,3,3
3,2,2,2
3,0,3,0
3,0,3,3
3,0,0,0
3,3,3,3
2,0,2,2
2,0,2,0
2,0,0,0
2,2,2,2
0,0,0,0
count=7
2,0,2,3,0,0,3
2,0,2,3,0,0,0
2,0,2,3,0,0,2
2,0,2,3,0,3,3
2,0,2,3,0,3,2
2,0,2,3,0,2,2
2,0,2,3,3,3,2
2,0,2,3,3,3,3
2,0,2,3,3,2,2
2,0,2,3,2,2,2
2,0,2,0,0,0,0
2,0,2,0,0,0,2
2,0,2,0,0,2,2
2,0,2,0,2,2,2
2,0,2,2,2,2,2
2,0,3,0,0,3,0
2,0,3,0,0,3,3
2,0,3,0,0,0,0
2,0,3,0,3,3,3
2,0,3,3,3,3,3
2,0,0,0,0,0,0
2,2,3,3,3,2,3
2,2,3,3,3,2,2
2,2,3,3,3,3,3
2,2,3,3,2,2,2
2,2,3,2,2,2,2
2,2,2,2,2,2,2
2,3,3,3,3,3,3
0,3,0,0,3,0,0
0,3,0,0,3,0,3
0,3,0,0,3,3,3
0,3,0,0,0,0,0
0,3,0,3,3,3,3
0,3,3,3,3,3,3
0,0,0,0,0,0,0
3,3,3,3,3,3,3
count=8
3,0,0,0,0,2,2,2
3,0,0,0,0,2,2,3
3,0,0,0,0,2,2,0
3,0,0,0,0,2,3,3
3,0,0,0,0,2,3,0
3,0,0,0,0,2,0,0
3,0,0,0,0,3,3,3
3,0,0,0,0,3,3,0
3,0,0,0,0,3,0,0
3,0,0,0,0,0,0,0
3,0,0,0,2,2,2,2
3,0,0,0,2,2,2,3
3,0,0,0,2,2,3,3
3,0,0,0,2,3,3,3
3,0,0,0,3,3,3,3
3,0,0,2,2,2,2,3
3,0,0,2,2,2,2,2
3,0,0,2,2,2,3,3
3,0,0,2,2,3,3,3
3,0,0,2,3,3,3,3
3,0,0,3,3,3,3,3
3,0,2,2,2,2,3,3
3,0,2,2,2,2,3,2
3,0,2,2,2,2,2,2
3,0,2,2,2,3,3,3
3,0,2,2,3,3,3,3
3,0,2,3,3,3,3,3
3,0,3,3,3,3,3,3
3,2,2,2,2,3,3,3
3,2,2,2,2,3,3,2
3,2,2,2,2,3,2,2
3,2,2,2,2,2,2,2
3,2,2,2,3,3,3,3
3,2,2,3,3,3,3,3
3,2,3,3,3,3,3,3
3,3,3,3,3,3,3,3
0,0,0,0,2,2,2,2
0,0,0,0,2,2,2,0
0,0,0,0,2,2,0,0
0,0,0,0,2,0,0,0
0,0,0,0,0,0,0,0
0,0,0,2,2,2,2,2
0,0,2,2,2,2,2,2
0,2,2,2,2,2,2,2
2,2,2,2,2,2,2,2

real    1m34.525s
user    1m32.524s
sys     0m0.030s
[download]

90 seconds wouldn't be so bad, since this is part of a larger script to generate datafiles that only really needs to be run once (to generate the file). But I'd rather not spend days waiting for it to finish for higher values of $states.

Any suggestions? Like I said, I'd prefer to stick to CPAN, but I'll take what I can get.

Thanks!