Related module surveys:: Partitions and combinations / permutations.

It looks like you want all the unique permutations of the 3-entry partitions. Using ntheory this could be done as:

use ntheory ":all";
my %seen;
forpart {
  my @p=@_;
  forperm {
    my $s="@p[@_]";
    say $s unless $seen{$s}++;
  } scalar(@p);
} 5,{n=>3};
[download]

forpart iterates over partitions, including restrictions (in this case that n must be exactly equal to 3). forperm does permutations, and we use a hash to remove all the duplicates since some entries are identical. This generates:

3 1 1
1 3 1
1 1 3
2 2 1
2 1 2
1 2 2
[download]

It agrees with Grandfather's program for examples such as 28/6 and 18/8. However, while it's quite nice for smaller values, all the permutations with duplicates make it slower for the larger examples -- we go through a huge number of permutations for a small number of unique values.

Edit: it's much faster than the variations_with_repetitions method, but GF's programs are even better. A better unique-permutations solution would help. Or, since hdb pointed out this is compositions, perhaps add a new function or as an option for 'forpart'.

Update: ntheory 0.56 on CPAN now:

$ perl -Mntheory=:all -E 'forcomp { say "@_" } 5,{n=>3}'
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1
[download]

Update 2: While the compositions iterator is the right solution, I looked into a better multiset permutations solution. The one I showed earlier (generate all permutations, collect unique ones) is simple and easy, but gets very slow. I implemented a simple multiset permutation iterator, so now we could do:

use ntheory ":all";
forpart {
    formultiperm {
        say "@_";
    } [@_];
} 5,{n=>3};
[download]

For larger sets, this runs a little faster than oiskuu's solve code, about the same as my PP compositions iterator, but slower than GF's second solution or my XS compositions iterator. It's all in PP for now.

---

---

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! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

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:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

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

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