Re: Faster alternative to Math::Combinatorics

[Laurent_R]

Hi AppleFritter,

you've already received good solutions for your problem, but I thought it might be beneficial to provide a basic algorithm to solve it. This is using recursion.

(I know I'm coming a bit late, but I did not have time yesterday to code and test anything.)

Anyway, this is my (first) solution:

use strict;
use warnings;


my @list = (0, 2, 3);
for my $w (1, 2, 3, 4, 7, 8) {
    print "count = $w\n";
    make_sets1($w, "");
}

sub make_sets1 {
    my ($weight, $temp_result) = @_;
    print "$temp_result\n" and return if $weight <= 0;
    for my $item (@list) {
        make_sets1( $weight -1, "$temp_result$item, ");
    }
}

If I run this, I get the following (abbreviated) output:

$ time perl  multisets.pl
count = 1
0,
2,
3,
count = 2
0, 0,
0, 2,
0, 3,
2, 0,
2, 2,
2, 3,
3, 0,
3, 2,
3, 3,
count = 3
0, 0, 0,
0, 0, 2,
0, 0, 3,
0, 2, 0,
0, 2, 2,
0, 2, 3,
0, 3, 0,
0, 3, 2,
0, 3, 3,
2, 0, 0,
2, 0, 2,
2, 0, 3,
2, 2, 0,
2, 2, 2,
2, 2, 3,
2, 3, 0,
2, 3, 2,
2, 3, 3,
3, 0, 0,
3, 0, 2,
3, 0, 3,
3, 2, 0,
3, 2, 2,
3, 2, 3,
3, 3, 0,
3, 3, 2,
3, 3, 3,
count = 4
0, 0, 0, 0,
0, 0, 0, 2,
0, 0, 0, 3,
0, 0, 2, 0,
0, 0, 2, 2,
0, 0, 2, 3,
0, 0, 3, 0,
0, 0, 3, 2,
0, 0, 3, 3,
0, 2, 0, 0,
0, 2, 0, 2,
0, 2, 0, 3,
0, 2, 2, 0,
0, 2, 2, 2,
0, 2, 2, 3,
0, 2, 3, 0,
0, 2, 3, 2,
0, 2, 3, 3,
0, 3, 0, 0,
0, 3, 0, 2,
0, 3, 0, 3,
0, 3, 2, 0,
0, 3, 2, 2,
0, 3, 2, 3,
0, 3, 3, 0,
0, 3, 3, 2,
0, 3, 3, 3,
2, 0, 0, 0,
2, 0, 0, 2,
2, 0, 0, 3,
2, 0, 2, 0,
2, 0, 2, 2,
2, 0, 2, 3,
2, 0, 3, 0,
2, 0, 3, 2,
2, 0, 3, 3,
2, 2, 0, 0,
2, 2, 0, 2,
2, 2, 0, 3,
2, 2, 2, 0,
2, 2, 2, 2,
2, 2, 2, 3,
2, 2, 3, 0,
2, 2, 3, 2,
2, 2, 3, 3,
2, 3, 0, 0,
2, 3, 0, 2,
2, 3, 0, 3,
2, 3, 2, 0,
2, 3, 2, 2,
2, 3, 2, 3,
2, 3, 3, 0,
2, 3, 3, 2,
2, 3, 3, 3,
3, 0, 0, 0,
3, 0, 0, 2,
3, 0, 0, 3,
3, 0, 2, 0,
3, 0, 2, 2,
3, 0, 2, 3,
3, 0, 3, 0,
3, 0, 3, 2,
3, 0, 3, 3,
3, 2, 0, 0,
3, 2, 0, 2,
3, 2, 0, 3,
3, 2, 2, 0,
3, 2, 2, 2,
3, 2, 2, 3,
3, 2, 3, 0,
3, 2, 3, 2,
3, 2, 3, 3,
3, 3, 0, 0,
3, 3, 0, 2,
3, 3, 0, 3,
3, 3, 2, 0,
3, 3, 2, 2,
3, 3, 2, 3,
3, 3, 3, 0,
3, 3, 3, 2,
3, 3, 3, 3,
count = 7
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 2,
0, 0, 0, 0, 0, 0, 3,
0, 0, 0, 0, 0, 2, 0,
0, 0, 0, 0, 0, 2, 2,
0, 0, 0, 0, 0, 2, 3,
0, 0, 0, 0, 0, 3, 0,
0, 0, 0, 0, 0, 3, 2,
0, 0, 0, 0, 0, 3, 3,
. . . (abbreviated)
3, 3, 3, 3, 3, 3, 0, 3,
3, 3, 3, 3, 3, 3, 2, 0,
3, 3, 3, 3, 3, 3, 2, 2,
3, 3, 3, 3, 3, 3, 2, 3,
3, 3, 3, 3, 3, 3, 3, 0,
3, 3, 3, 3, 3, 3, 3, 2,
3, 3, 3, 3, 3, 3, 3, 3,

real    0m0.141s
user    0m0.046s
sys     0m0.031s

Or, redirecting the output:

$ time perl  multisets.pl > /dev/null

real    0m0.057s
user    0m0.015s
sys     0m0.015s

So, this is pretty fast.

Now, there is a slight problem. This program is not producing the same results as those you appear to be expecting (I am not talking about the different formatting, but about the number and list of results).

For example, looking only at the weight of 3, I get this:

count = 3
0, 0, 0,
0, 0, 2,
0, 0, 3,
0, 2, 0,
0, 2, 2,
0, 2, 3,
0, 3, 0,
0, 3, 2,
0, 3, 3,
2, 0, 0,
2, 0, 2,
2, 0, 3,
2, 2, 0,
2, 2, 2,
2, 2, 3,
2, 3, 0,
2, 3, 2,
2, 3, 3,
3, 0, 0,
3, 0, 2,
3, 0, 3,
3, 2, 0,
3, 2, 2,
3, 2, 3,
3, 3, 0,
3, 3, 2,
3, 3, 3,

whereas you seem to be expecting:

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

I get 27 combinations and you seem to be expecting only 10. I don't understand, for example, why you have only one result starting with 2, why you don't have (2,0,0),  (2,0,2),  (2,0,3),   (2,2,0), ... and so on. I would expect you to be willing to have all the possible combinations with repetitions (i.e. 3 ** 3 = 27 combinations), but that doesn't appear to be what you're after. Or is there an error in your expected result? Or did I miss part of your explanation?

I'll make another post with a modified program which appears to produce something closer to what you seem to be expecting.

Update: Modified the list of "missing" combinations listed just above to reflect the input data (O, 2, 3 and not 0, 1, 2).

[AppleFritter]

More answers and solutions are always good, so thanks a lot for your effort!

The reason you're getting 27 combinations is that you're producing ordered tuples, whereas what I'm looking for is multisets (which are by definition unordered). I'll quote what I wrote in my post:

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.

What this means is that:

• Results that contain the same numbers a different amount of times are distinguished: "2,3,3" is not the same as "2,2,3".
• Results that are merely reordered are NOT distinguished: "2,3,3" is the same as "3,2,3" and "3,3,2".

Wikipedia has more on multisets: Multiset.

Like I said in my reply to tybalt89, the underlying problem I was trying to solve here¹ is related to a certain class of cellular automata with multiple states. I needed to generate all the possible combinations of states a certain subset of a given cell's immediate neighborhood could be in — but I was only interested in outer-totalistic CAs where the specific alignment of those neighboring cells didn't matter. Hence: it makes a difference whether of three cells I'm considering, one is in state 2 and two in state 3, or two in state 2 and one in state 3; but it doesn't make a difference specifically where in the center cell's neighborhood those neighboring cells are. Multisets / multicombinations were a natural choice for representing that.

TL;DR — thanks again, I appreciate all the good replies, tips, pointers and suggestions I got!

Footnotes:

1. And which I have solved; it turns out that Algorithm::Combinatorics not only has a convenient function (combinations_with_repetitions) to generate just what I need, that function is also blindingly fast. See my reply to BrowserUk who also misunderstood (or didn't read carefully, one imagines) my question.

[Laurent_R]

OK, AppleFritter, thanks for your answer.

Thinking more about it, what I get with this program is actually 27 permutations, not 27 combinations. But English is not my mother tongue (and, as far as I can say, probably also not yours), so I probably got a bit confused about it. And I did not know anything about multisets before (or had forgotten everything about it).

Thanks a lot for the clarification.

I haven't checked thoroughly, but it seems that the program I have suggested in my other post (http://www.perlmonks.org/?node_id=1198576) probably does what you want.

Update: And, BTW, my code in the other post runs in less than 1/20th of a second, so it is also fairly fast.