Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Combinatorics problem. (Updated with more info.)

by danaj (Friar)
on Dec 12, 2015 at 07:15 UTC ( [id://1150100] : note . print w/replies, xml ) Need Help??


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

I added a forcomp iterator to ntheory, and changed to Kelleher's RuleAsc algorithm from ZS1. The changes to support both compositions and partitions are minimal. This means lexicographic ordering for both (vs. anti-lexico), which I think fits in better with the same ordering for combinations and permutations. It has the same restriction options as partitions (min/max for both length and value). It's on github, not sure when it'll hit CPAN. (update: it's on CPAN now as version 0.56)

Some timings of various solutions on this thread, for larger values. Macbook Pro, Perl 5.22.0. Other sizes may give different results, each solution has different tradeoffs, etc. I thought it was interesting.

Method24,6
(33649)
24,7
(100947)
24,9
(490314)
Comments
buk update83.118 min---var with rep, test with List::Util::sum
tye0.501.437.47Alg::Loops
anon-hack20.241.044.18Alg::Comb combinations
oiskuu20.351.014.30Alg::Comb var with rep
GF10.311.067.04GrandFather's first code
danaj10.180.9759.8ntheory unique perms of partitions. Ouch on 24,9.
danaj2-pp0.160.401.82New ntheory forcomp in Perl
oiskuu10.130.352.61Recursive 'solve' code based on GF
GF20.080.131.02GrandFather's second code
danaj20.050.120.49New ntheory forcomp in XS