fast vector partitions algorithm

[Denis]

This is a re-post from sage-combinat-devel with the same subject. Please post answers there.

I have translated the Haskell code for vector partitions by M. C. Er, The Computer Journal, Vol. 31, 1988, 283-284, into Python (2 or 3, stand-alone file with 60 lines total).

The code works significantly faster than the Sage implementation:

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.0, Release Date: 2020-01-01                     │
│ Using Python 3.7.3. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
sage: import vpartitions
sage: %time myvparts=vpartitions.vPartitionso([6,6,6])
CPU times: user 9.13 s, sys: 89.8 ms, total: 9.22 s
Wall time: 9.22 s
sage: %time sagevparts=list(VectorPartitions([6,6,6]))
CPU times: user 2min 10s, sys: 177 ms, total: 2min 10s
Wall time: 2min 10s
sage: myvparts[::-1]==sagevparts
True

If someone would take over the job of contributing this code to Sage, I would be glad to help. There are a few caveats:

1) the code is recursive;

2) there is no "min" option like in the Sage implementation.

I do not know how difficult (or necessary) it would be to address these points.

Of course, anyone can take it up straight from Er's paper instead, I won't be jealous:)

Cheers,

Denis

[Dima Pasechnik]

Hi Denis,

On Thu, Feb 13, 2020 at 5:08 PM Denis <denis...@gmail.com> wrote:
>
> This is a re-post from sage-combinat-devel with the same subject. Please post answers there.
>
> I have translated the Haskell code for vector partitions by M. C. Er, The Computer Journal, Vol. 31, 1988, 283-284, into Python (2 or 3, stand-alone file with 60 lines total).
>
> The code works significantly faster than the Sage implementation:
>
> ┌────────────────────────────────────────────────────────────────────┐
> │ SageMath version 9.0, Release Date: 2020-01-01 │
> │ Using Python 3.7.3. Type "help()" for help. │
> └────────────────────────────────────────────────────────────────────┘
> sage: import vpartitions
> sage: %time myvparts=vpartitions.vPartitionso([6,6,6])
> CPU times: user 9.13 s, sys: 89.8 ms, total: 9.22 s
> Wall time: 9.22 s
> sage: %time sagevparts=list(VectorPartitions([6,6,6]))
> CPU times: user 2min 10s, sys: 177 ms, total: 2min 10s
> Wall time: 2min 10s
> sage: myvparts[::-1]==sagevparts
> True
>
> If someone would take over the job of contributing this code to Sage, I would be glad to help. There are a few caveats:

the normal thing to got forward with is would be to open a trac ticket
for the task
(you'd need a GitHub account for this)
and post your code there, e.g. as an attachment.

>
> 1) the code is recursive;

nothing wrong with this, per se.

> 2) there is no "min" option like in the Sage implementation.
>
> I do not know how difficult (or necessary) it would be to address these points.
>
> Of course, anyone can take it up straight from Er's paper instead, I won't be jealous:)

Thanks for looking into this.

>
> Cheers,
>
> Denis
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/5b1ee47a-7575-4ba9-853a-7e96e400e2e5%40googlegroups.com.

[Denis]

 

I have made a mistake in the original post.

EDIT: this reference was wrong the original post

--- by M. C. Er, The Computer Journal, Vol. 31, 1988, 283-284,

CORRECTION: the reference for the Haskell source should read

+++ by Brent Yorgey,The Monad.Reader Issue 8 , September 10, 2007

Sorry about that - I had read several papers on the subject a while ago and simply forgot which one I implemented.

I will open a trac ticket ASAP.

Thanks for the advice,

Denis

[Denis]

Thanks for the encouragement.

I have opened a trac ticket now. I will push the branch as soon as I sort some things out. (I asked for help with git under sage-combinat-devel, not necessary to repeat here.)

Denis