Partitions parts_in vs WeightedIntegerVectors

[tomgrubbmath]

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.

CC: @slel @videlec @seblabbe

Component: number theory

Keywords: Partitions

Author: Frédéric Chapoton, Tom Grubb

Branch/Commit: ea494b1

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/31319

[tomgrubbmath]

Author: Tom Grubb

[slel]

comment:2

Thanks for opening this ticket and suggesting an approach.

[fchapoton]

New commits:

bec5165

iterator for partitions with constraints

[fchapoton]

Changed author from Tom Grubb to Frédéric Chapoton, Tom Grubb

[fchapoton]

Branch: u/chapoton/31319

[fchapoton]

Commit: bec5165

[tscrim]

comment:6

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.

[sagetrac-git]

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

ea494b1

trac 31319 better iterator

[sagetrac-git]

Changed commit from bec5165 to ea494b1

[fchapoton]

comment:8

Thanks, Travis. I made the suggested changes.

[tscrim]

comment:9

Thank you. LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from u/chapoton/31319 to ea494b1