#31319 closed enhancement (fixed)

Partitions parts_in vs WeightedIntegerVectors

Reported by: Tom Grubb Owned by:
Priority: minor Milestone: sage-9.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:

Status badges

Description (last modified by Samuel Lelièvre)

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])))
a = time.time()
i = 0
L = []
while time.time() - a < 100:
    i += 1
    L.append(len(Partitions(i, parts_in=[1000, 1001])))

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])):
a = time.time()
for i in range(1000*1001, 0, -1):
    if any(_ for _ in Partitions(i, parts_in=[1000, 1001])):

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]

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 Tom Grubb

Authors: Tom Grubb

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

Cc: Samuel Lelièvre added
Description: modified (diff)

Thanks for opening this ticket and suggesting an approach.

comment:3 Changed 22 months ago by Frédéric Chapoton

Authors: Tom GrubbFrédéric Chapoton, Tom Grubb
Branch: u/chapoton/31319
Commit: bec51659b5e1210a78b7a103e1353da208630d11
Status: newneeds_review

New commits:

bec5165iterator for partitions with constraints

comment:4 Changed 22 months ago by Frédéric Chapoton

Cc: Vincent Delecroix added

comment:5 Changed 22 months ago by Frédéric Chapoton

Cc: Sébastien Labbé added

comment:6 Changed 22 months ago by Travis Scrimshaw

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 k-regular/restricted partitions as well, but that can be a separate ticket.

comment:7 Changed 22 months ago by git

Commit: bec51659b5e1210a78b7a103e1353da208630d11ea494b13169d4e57803b59f53e1080ca8a0b466e

Branch pushed to git repo; I updated commit sha1. New commits:

ea494b1trac 31319 better iterator

comment:8 Changed 22 months ago by Frédéric Chapoton

Thanks, Travis. I made the suggested changes.

comment:9 Changed 22 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Thank you. LGTM.

comment:10 Changed 21 months ago by Volker Braun

Branch: u/chapoton/31319ea494b13169d4e57803b59f53e1080ca8a0b466e
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.