Math::Partitions 
Author Message
 Math::Partitions

A few months ago there was was a discussion on clp.misc
about how to construct a random partition of a number n
into k parts.  Here's the (unwrapped) url:

http://www.*-*-*.com/ %40mumonkan.sun...

Today I got around to converting the subs to XS- they're
about 10 times faster than the Perl versions.  I was not
able to find another package with the same subs on CPAN,
so I'd like to upload these. Right now, there's just two
functions:

parts(n,k)-
  returns the total number of partitions of n into k parts;
  unless k is absent, in which case it returns the total number
  of partitions of n (i.e. a sum over k <= n).

rand_part(n,k)-
  returns a random partition of n into k parts (here "random"
  means equiprobable over all possible such partitions). If k
  is absent, make it over all possible partitions of n.

I'm thinking of calling it Math::Partitions, but perhaps there's
a better name.  

Any ideas?

--
Joe Schaefer



Sun, 18 Apr 2004 05:38:03 GMT  
 Math::Partitions

Quote:

>parts(n,k)-
>  returns the total number of partitions of n into k parts;
>  unless k is absent, in which case it returns the total number
>  of partitions of n (i.e. a sum over k <= n).

>rand_part(n,k)-
>  returns a random partition of n into k parts (here "random"
>  means equiprobable over all possible such partitions). If k
>  is absent, make it over all possible partitions of n.

>I'm thinking of calling it Math::Partitions, but perhaps there's
>a better name.  

Sounds like a potentially useful module, and the name seems fine to me
as well.  I'd prefer the function names to have "ition" after "part",
even at the cost of extra typing, but that's just my personal taste.

You probably want to mention the words "Stirling number" and "Bell
number" somewhere in the documentation, so that any mathematicians
who've had to memorize those names can spot them.  Might help with
keyword searches, too.

--
Ilmari Karonen -- http://www.sci.fi/~iltzu/
"Get real!  This is a discussion group, not a helpdesk.  You post something,
we discuss its implications.  If the discussion happens to answer a question
you've asked, that's incidental."           -- nobull in comp.lang.perl.misc



Mon, 19 Apr 2004 06:42:07 GMT  
 Math::Partitions

Quote:


>>parts(n,k)-
>>  returns the total number of partitions of n into k parts;
>>  unless k is absent, in which case it returns the total number
>>  of partitions of n (i.e. a sum over k <= n).
 [snip]
>You probably want to mention the words "Stirling number" and "Bell
>number" somewhere in the documentation, so that any mathematicians
>who've had to memorize those names can spot them.  Might help with
>keyword searches, too.

Now that I re-read your post after getting some much-needed sleep, I see
that you're talking about partitions of an integer, when I thought you
were talking about partitions of a set (a different, and rather simpler,
problem).  Sorry for any confusion.

In any case, it could be nice to eventually expand the module to
efficiently compute all sorts of related combinatorical quantities.

--
Ilmari Karonen -- http://www.sci.fi/~iltzu/
"Get real!  This is a discussion group, not a helpdesk.  You post something,
we discuss its implications.  If the discussion happens to answer a question
you've asked, that's incidental."           -- nobull in comp.lang.perl.misc



Tue, 20 Apr 2004 04:29:45 GMT  
 Math::Partitions

Quote:

> Now that I re-read your post after getting some much-needed sleep, I see
> that you're talking about partitions of an integer, when I thought you
> were talking about partitions of a set (a different, and rather simpler,
> problem).  Sorry for any confusion.

Which one is simpler? :)

Quote:
> In any case, it could be nice to eventually expand the module to
> efficiently compute all sorts of related combinatorical quantities.

That's what I did when I read your original comments.  I've added
Binomial, Bell and Stirling2 functions, but what still remains is a
random partition generator for sets.  I'm struggling a bit with the
interface, so if you have any advice I'd appreciate it.

What I'm considering is overloading the aforementioned rand_part() to
take an arrayref and partition it randomly into a list of anonymous arrays:



and similarly


Does anyone have a better suggestion?

--
Joe Schaefer     "Never put off until tomorrow that which can be done the day
                                       after tomorrow."
                                               --Mark Twain



Tue, 20 Apr 2004 05:48:08 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. ANNOUNCE: Math::Polynomial and Math::Interpolate version 0.01

2. RFC: Math::Date and Math::Currency

3. RFC: Math::Vector and Math::Vector::Vector3D

4. OS/2 Perl: hangs on HPFS partition?

5. Remaining space on a partition

6. module for combinatorics? (partitions etc)

7. setting volume label for a partition

8. Getting partition size from perl script

9. partition a large file into a number of small ones

10. Generating the partitions of a string

11. partitioning binary files

12. Q: generating set partitions

 

 
Powered by phpBB® Forum Software