bug in Permutations_msetk cardinality

[videlec]

sage: P = Permutations([1,1,1,2,2,2,3,3,3], 3)
sage: P.cardinality()
1680
sage: _ = P.list()
sage: P.cardinality()
27

See the original report on this sage-support thread

CC: @tscrim @videlec @vinklein

Component: combinatorics

Keywords: bug

Author: Frédéric Chapoton

Branch/Commit: bdd22a2

Reviewer: Travis Scrimshaw

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

[tscrim]

comment:1

This seems to be a problem of it inheriting the cardinality from Permutations_mset. The simple fix is to just have

def cardinality(self):
    return len(self.list())

Or does anyone know of a easy-ish formula?

[videlec]

comment:2

Replying to @tscrim:

This seems to be a problem of it inheriting the cardinality from Permutations_mset.

It is.

The simple fix is to just have

def cardinality(self):
    return len(self.list())

Or does anyone know of a easy-ish formula?

I don't understand why there are two classes at all. Permutations_mset(ms) is a shortcut for Permutations_msetk(ms, len(ms)).

[tscrim]

comment:3

Replying to @videlec:

I don't understand why there are two classes at all. Permutations_mset(ms) is a shortcut for Permutations_msetk(ms, len(ms)).

I don't see anything like that in the code. Or do you mean there should be? I think there should be 2 classes, as the general Permutations_mset can have faster iteration, a dedicated cardinality method, and easier/faster containment checking. Although I am thinking the better approach would be to have a common ABC for P_mset and P_msetk as basically every method of the former is overwritten by the latter.

[videlec]

comment:4

Replying to @tscrim:

Replying to @videlec:

I don't understand why there are two classes at all. Permutations_mset(ms) is a shortcut for Permutations_msetk(ms, len(ms)).

I don't see anything like that in the code.

Me neither. Replace shortcut by "the same mathematical set".

On the other hand P_msetk is a union of P_mset over the submultiset of fixed size.

Or do you mean there should be? I think there should be 2 classes, as the general Permutations_mset can have faster iteration, a dedicated cardinality method, and easier/faster containment checking. Although I am thinking the better approach would be to have a common ABC for P_mset and P_msetk as basically every method of the former is overwritten by the latter.

Adding a third class to "simplify" the inheritance!?

The _k suffix in the name of classes is very confusing:

• Subsets_s(s) is the union of the Subsets_sk(s, k)
• Permutations_n(n) is the same thing as Permutations_nk(n, n)

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

comment:5

Here is a bugfix, plus using libgap instead of gap

---

New commits:

bdd22a2

fix some details in permutations of multisets

[fchapoton]

Commit: bdd22a2

[fchapoton]

Branch: u/chapoton/20317

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:6

I think this will work for now. Thanks.

[mantepse]

comment:7

I shouldn't be doing this...

(and I am guessing that the part to obtain the multiplicities, which I stole from Permutations_mset.cardinality is not ideal)

def cardinality(self):
    """
    
    EXAMPLES::

        sage: M = [randint(1, 4) for k in range(20)]
        sage: P = Permutations(M, 5)
        sage: len(list(P)) == c(P)
        True
    """
    lmset = list(self.mset)
    mset_list = [lmset.index(x) for x in lmset]
    d = {}
    for i in mset_list:
        d[i] = d.get(i, 0) + 1

    M = list(d.values())
    s = 0
    for m in IntegerVectors(self._k, len(M), outer=M):
        s += multinomial(m)
    return s

[vbraun]

Changed branch from u/chapoton/20317 to bdd22a2