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

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		`&`
	<		`<`
	>		`>`
	[		`[`
	]		`]`

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.