comment on

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, ");
    }
}
[download]

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
[download]

Or, redirecting the output:

$ time perl  multisets.pl > /dev/null

real    0m0.057s
user    0m0.015s
sys     0m0.015s
[download]

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,
[download]

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
[download]

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).

In reply to Re: Faster alternative to Math::Combinatorics by Laurent_R
in thread Faster alternative to Math::Combinatorics by AppleFritter

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


No such thing as a small change
	PerlMonks