Counting integer compositions with restrictions

[Jori Mäntysalo (TAU)]

Is there a fast way to compute for example

Compositions(15, min_length=10, max_length=10).cardinality()

in some package already integrated to SageMath? For Partitions(...) that
seems to be the case, but Compositions(...) uses just brute enumeration.

--
Jori Mäntysalo

Tampereen yliopisto - Ihminen ratkaisee

[Martin R]

I do think that P = Partitions(15, min_length=10, max_length=10); P.cardinality() also uses brute force. (at least P.cardinality?? says so).

Would be great, though!

Martin

[Martin R]

I am guessing that it should be sufficiently fast to compute the cardinality using the generating series.  That is, for compositions with parts in a set S this would be

1/(1-sum_{s in S} x^s)

with special cases S = {a,...,b} and S = {a,...}

Martin

[TB]

There is the cardinality method of IntegerVectors. Note that the default
for min_part is 0.

It is implemented in src/sage/combinat/integer_vector.py without brute
force enumeration under some constraints. Looking at it now, I think
there is a bug at line 1331: It will never enter the if clause there and
always continue with brute force, because if the length (=self.k) is not
None and there is a max_part constraint, then there are at least two
constraints...

Indeed, it would be great for Compositions and IntegerVectors to do the
right thing.

Regards,
TB

> --
> 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
> <mailto:sage-devel+...@googlegroups.com>.
> To post to this group, send email to sage-...@googlegroups.com
> <mailto:sage-...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Vincent Delecroix]

Le 19/02/2019 à 21:43, Jori Mäntysalo (TAU) a écrit :
> Is there a fast way to compute for example
>
> Compositions(15, min_length=10, max_length=10).cardinality()
>
> in some package already integrated to SageMath? For Partitions(...) that
> seems to be the case, but Compositions(...) uses just brute enumeration.

Even worse is

Compositions(50, length=10).cardinality()

that is trivial (a binomial coefficient). It would be *very* nice to
improve this. Please put me in cc if you open tickets.

Vincent

[Martin R]

I just realised that `Compositions` and `IntegerListLex` do not seem to support generation of lists whose entries are in a specified set.  I admit that I'm not sure it would be worth it.

Martin

[Jori Mäntysalo (TAU)]

On Tue, 19 Feb 2019, TB wrote:

> There is the cardinality method of IntegerVectors. Note that the default for
> min_part is 0.

So this could be used for...?

I do not know the area. I was just playing with numbers (original question
was "In how many ways you can arrange a queue of 9 men and 7 women such
that no two women are next to each other?"), and noticed that
.cardinality() in sage/combinat/partition.py even has algorithm-parameter.
So I think there might be existing code just waiting for interface.

[Travis Scrimshaw]

One example where enumeration of these (with say a fixed sum) is useful is for computing ordered set partitions by breaking the problem up into sets of fixed sizes.

Best,

Travis

[TB]

On 21/02/2019 9:59, Jori Mäntysalo (TAU) wrote:
> On Tue, 19 Feb 2019, TB wrote:
>
>> There is the cardinality method of IntegerVectors. Note that the default for
>> min_part is 0.
>
> So this could be used for...?
>
> I do not know the area. I was just playing with numbers (original question
> was "In how many ways you can arrange a queue of 9 men and 7 women such
> that no two women are next to each other?"), and noticed that
> .cardinality() in sage/combinat/partition.py even has algorithm-parameter.
> So I think there might be existing code just waiting for interface.
>

A composition can be thought as an integer vector with only natural
numbers. So theoretically Compositions() could have been implemented
using IntegerVectors(), which has a (buggy?) cardinality method that
does use binomials coefficients, and not just naive brute force. For
example:

sage: Compositions(10, length=6).cardinality()
126
sage: IntegerVectors(10, length=6, min_part=1).cardinality()
126

I do not know the exact reasons/history of implementation of
combinatorial objects in Sage. Some of those are now using
IntegerListsLex for enumeration with naive counting, as you noticed.

Regards,
TB