# Partitions parts_in vs WeightedIntegerVectors

Reported by: Owned by: Tom Grubb minor sage-9.3 number theory Partitions Samuel Lelièvre, Vincent Delecroix, Sébastien Labbé Frédéric Chapoton, Tom Grubb Travis Scrimshaw N/A ea494b1 ea494b13169d4e57803b59f53e1080ca8a0b466e

### 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])))
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.

### 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 modified (diff)

Thanks for opening this ticket and suggesting an approach.

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

Authors: Tom Grubb → Frédéric Chapoton, Tom Grubb → u/chapoton/31319 → bec51659b5e1210a78b7a103e1353da208630d11 new → needs_review

New commits:

 ​bec5165 `iterator 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: bec51659b5e1210a78b7a103e1353da208630d11 → ea494b13169d4e57803b59f53e1080ca8a0b466e

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

 ​ea494b1 `trac 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 needs_review → positive_review

Thank you. LGTM.

### comment:10 Changed 21 months ago by Volker Braun

Branch: u/chapoton/31319 → ea494b13169d4e57803b59f53e1080ca8a0b466e → fixed positive_review → closed
Note: See TracTickets for help on using tickets.