Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1150100]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (5)
As of 2024-03-29 07:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found