Opened 22 months ago
Closed 21 months ago
#31319 closed enhancement (fixed)
Partitions parts_in vs WeightedIntegerVectors
Reported by:  Tom Grubb  Owned by:  

Priority:  minor  Milestone:  sage9.3 
Component:  number theory  Keywords:  Partitions 
Cc:  Samuel Lelièvre, Vincent Delecroix, Sébastien Labbé  Merged in:  
Authors:  Frédéric Chapoton, Tom Grubb  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  ea494b1 (Commits, GitHub, GitLab)  Commit:  ea494b13169d4e57803b59f53e1080ca8a0b466e 
Dependencies:  Stopgaps: 
Description (last modified by )
Creating the integer partitions of an integer N
with parts restricted to a list L
takes much longer than creating the weighted integer vectors of N
with weights in L
. In principle one should be able to translate between these two constructions, so perhaps it would be better to compute Partitions(N, parts_in=L)
by calling WeightedIntegerVectors(N, L)
and then transferring the results accordingly? Below are two examples where this manifests.
This code sees how far Sage can compute in 100 seconds with respect to both functions:
import time a = time.time() i = 0 L = [] while time.time()  a < 100: i += 1 L.append(len(WeightedIntegerVectors(i, [1000, 1001]))) print(len(L))
a = time.time() i = 0 L = [] while time.time()  a < 100: i += 1 L.append(len(Partitions(i, parts_in=[1000, 1001]))) print(len(L))
The result of the first block is 321269, whereas the second is 41686 (for me).
Another example: this code computes the Frobenius number of [1000, 1001]
(https://en.wikipedia.org/wiki/Coin_problem) by starting at the naive upper bound and working downwards:
import time a = time.time() for i in range(1000*1001, 0, 1): if any(_ for _ in WeightedIntegerVectors(i, parts_in=[1000, 1001])): pass else: print(i) break
a = time.time() for i in range(1000*1001, 0, 1): if any(_ for _ in Partitions(i, parts_in=[1000, 1001])): pass else: print(i) break
The first code block runs in 0.83 seconds whereas the second takes 249.96 seconds to evaluate (for me).
A very basic attempt at a fix for this would be something like
def PartitionPartsIn(N, L): sortL = sorted(L, reverse=True) for wIV in WeightedIntegerVectors(N, sortL): a = [] for i in range(len(sortL)): a += [sortL[i]]*wIV[i] yield(a)
Of course this would have to be adapted into the Partitions class, but it seems like that should be no issue as long as the parts_in
flag is taken into account. Even this crude fix gives me much better performance on the two tasks above.
Change History (10)
comment:1 Changed 22 months ago by
Authors:  → Tom Grubb 

comment:2 Changed 22 months ago by
Cc:  Samuel Lelièvre added 

Description:  modified (diff) 
comment:3 Changed 22 months ago by
Authors:  Tom Grubb → Frédéric Chapoton, Tom Grubb 

Branch:  → u/chapoton/31319 
Commit:  → bec51659b5e1210a78b7a103e1353da208630d11 
Status:  new → needs_review 
New commits:
bec5165  iterator for partitions with constraints

comment:4 Changed 22 months ago by
Cc:  Vincent Delecroix added 

comment:5 Changed 22 months ago by
Cc:  Sébastien Labbé added 

comment:6 Changed 22 months ago by
You can make this even faster by using the iterator_fast
function in integer_vector_weighted.py
. That way you don't have an additional transient element, just lists being returned. So I would do it like this:
from sage.combinat.integer_vector_weighted import iterator_fast sorted_parts = sorted(parts, reverse=True) for vec in iterator_fast(n, sorted_parts): yield sum([pi] * multi for pi, multi in zip(sorted_parts, vec), []
This should be the fastest way to do things.
This probably can be easily modified to work for kregular/restricted partitions as well, but that can be a separate ticket.
comment:7 Changed 22 months ago by
Commit:  bec51659b5e1210a78b7a103e1353da208630d11 → ea494b13169d4e57803b59f53e1080ca8a0b466e 

Branch pushed to git repo; I updated commit sha1. New commits:
ea494b1  trac 31319 better iterator

comment:9 Changed 22 months ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Thank you. LGTM.
comment:10 Changed 21 months ago by
Branch:  u/chapoton/31319 → ea494b13169d4e57803b59f53e1080ca8a0b466e 

Resolution:  → fixed 
Status:  positive_review → closed 
Thanks for opening this ticket and suggesting an approach.