Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re: Combinatorics problem.

by danaj (Friar)
on Dec 11, 2015 at 09:25 UTC ( [id://1149998] : note . print w/replies, xml ) Need Help??

in reply to Combinatorics problem. (Updated with more info.)

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};

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

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

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};
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.