About SetPartition.to_permutation

[Nathann Cohen]

Hello everybody,

Because of #19737 [1] (which was just opened) I learned the existence
of SetPartition.to_permutation.

A SetPartition object represents, as expected, a partition of a given
set. For FindSt---- some reason, there is a function turning it into a
permutation object [2], added in #14140 [3].

I do not see how this function can be defined mathematically and so I
write here to ask what you think we should do about it. Remove it?
Rename it? Move it to some other class?

Thanks,

Nathann

[1] http://trac.sagemath.org/ticket/19737

[2] Which raises an exception when one defines a partition of a set
which is not a set of integers:

sage: SetPartition([{'a','b','c'}]).to_permutation()
...
TypeError: cannot concatenate 'str' and 'int' objects

[3] http://trac.sagemath.org/ticket/14140

[Vincent Delecroix]

If you have an *ordered set* there is a canonical way to define one
permutation from a partition. You make it so that the atom of the
partitions are your cycles. And you order the cycle given by your order.
As an example

sage: p = SetPartition([[1,2,4],[3,5]]).to_permutation()
sage: p
[2, 4, 5, 1, 3]
sage: p.to_cycles()
[(1, 2, 4), (3, 5)]

There should also be Permutation.to_set_partition that gives the
partition of the space.

That being said: .to_permutation (and .to_whatever in general) are
terrible names.

Vincent

[Nathann Cohen]

> If you have an *ordered set* there is a canonical way to define one
> permutation from a partition. You make it so that the atom of the partitions
> are your cycles.

Yeah, sort everything. Wonder when something like that can be useful.
This being said, this class does not assume that the ground set is
totally ordered, so having this here is not possible.

> That being said: .to_permutation (and .to_whatever in general) are terrible
> names.

Don't make me answer that.

So, what do you advise we should do with this function?

Nathann

[Martin R]

Am Donnerstag, 17. Dezember 2015 14:12:06 UTC+1 schrieb Nathann Cohen:

> If you have an *ordered set* there is a canonical way to define one
> permutation from a partition. You make it so that the atom of the partitions
> are your cycles.

Yeah, sort everything. Wonder when something like that can be useful.
This being said, this class does not assume that the ground set is
totally ordered, so having this here is not possible.

How can we check that the ground set is totally ordered?  Given such a check, we could simply raise an error if it's not totally ordered, no?

I'd like to stress that I did not use the method in a findstat context (no idea why it would matter though), but rather to test a conjecture.  It's a entirely natural map.  At the very least, the map SetPartition.standard_form() is a classical map in combinatorics, used for example in the context of non crossing set partitions.

Martin

[Nathann Cohen]

Hello,

> How can we check that the ground set is totally ordered?

No idea. Furthermore, a set could be "totally ordered" because Python
compares the elements according to their memory address. That's a
total order, but totally unreliable as well.

> Given such a
> check, we could simply raise an error if it's not totally ordered, no?

You mean that SetPartition would have a .to_partition method, but that
this method would only work if some additional assumption is made on
SetPartition? Honestly I would prefer all SetPartition methods to work
on all SetPartition instances. Maybe it could be moved to another --
more specific -- class ?

> I'd like to stress that I did not use the method in a findstat context (no
> idea why it would matter though), but rather to test a conjecture. It's a
> entirely natural map. At the very least, the map
> SetPartition.standard_form() is a classical map in combinatorics, used for
> example in the context of non crossing set partitions.

It is probably well-defined when the ground set consists of integers,
but that is not an assumption that can be made in this class. Maybe
what you need in an "IntegerSetPartition" ?

Nathann

[Travis Scrimshaw]

> How can we check that the ground set is totally ordered?

No idea. Furthermore, a set could be "totally ordered" because Python
compares the elements according to their memory address. That's a
total order, but totally unreliable as well.

   There is sort of a way to do this in Python2 by looking to see if there is a __cmp__, but that is going away in Python3. Also, with how we do things in Sage (in particular, applying coercion in Element as a default), this will often not result in a valid check. Note that this is intrinsically an assumption on the method, not on the class.

> Given such a
> check, we could simply raise an error if it's not totally ordered, no?

You mean that SetPartition would have a .to_partition method, but that
this method would only work if some additional assumption is made on
SetPartition? Honestly I would prefer all SetPartition methods to work
on all SetPartition instances. Maybe it could be moved to another --
more specific -- class ?

That would completely over-engineer things, be backwards incompatible, and would make users hate us. This is why we have exceptions.
 

> I'd like to stress that I did not use the method in a findstat context (no
> idea why it would matter though), but rather to test a conjecture.  It's a
> entirely natural map.  At the very least, the map
> SetPartition.standard_form() is a classical map in combinatorics, used for
> example in the context of non crossing set partitions.

It is probably well-defined when the ground set consists of integers,
but that is not an assumption that can be made in this class. Maybe
what you need in an "IntegerSetPartition" ?

It is well-defined as there is a canonical bijection from the ground set X to {1, 2, ..., |X|} because of the total ordering. So the result of to_permutation would just not be a "standard permutation".

 Best,
Travis

[Nathann Cohen]

> That would completely over-engineer things, be backwards incompatible, and
> would make users hate us. This is why we have exceptions.

Stick to that "would make users hate us" thought and look at what we have:

- A method that "sometimes work, and sometimes does not", because it
does not apply to all instances of its class

- Mathematically speaking, this method cannot even be *defined* on the
object to which it belongs (the order does not always exist)

- No documentation of whenever this function can be expected to work
(in particular no warning)

- Unclear error message when it fails:

sage: SetPartition([{'a','b','c'}]).to_permutation()
...
TypeError: cannot concatenate 'str' and 'int' objects

If what I propose is "over engineering", do you have anything better?

Nathann

[Travis Scrimshaw]

Hey Nathann,

On Thursday, December 17, 2015 at 8:33:48 PM UTC-6, Nathann Cohen wrote:

> That would completely over-engineer things, be backwards incompatible, and
> would make users hate us. This is why we have exceptions.

Stick to that "would make users hate us" thought and look at what we have:

- A method that "sometimes work, and sometimes does not", because it
does not apply to all instances of its class

It is perfectly valid for a method to raise an error if the current instance does not meet certain criteria. I feel a double standard here with multiedges and loops...

- Mathematically speaking, this method cannot even be *defined* on the
object to which it belongs (the order does not always exist)

It has a perfectly valid and useful definition with a very mild assumption.

- No documentation of whenever this function can be expected to work
(in particular no warning)

I don't mind adding a *little* warning to the doc.

- Unclear error message when it fails:

    sage: SetPartition([{'a','b','c'}]).to_permutation()
    ...
    TypeError: cannot concatenate 'str' and 'int' objects

This will be fixed by the warning above. Although I would actually argue that this implementation cuts a few too many corners in this case.

If what I propose is "over engineering", do you have anything better?

One or two warnings along with a little bit of coding to improve things without throwing fud all over something.

BTW, the only messages complaining about this I've seen is from you.

Best,
Travis

[Nathann Cohen]

Yo,

> It is perfectly valid for a method to raise an error if the current instance
> does not meet certain criteria. I feel a double standard here with
> multiedges and loops...

If you consider it my responsibility to write, fix and manage the
loops/mutiedges code for graphs we have a problem. It is something
that YOU use and that I must manage ? Funny. Let me, and loops and
multiedges are gone from Sage tomorrow.

>> - Mathematically speaking, this method cannot even be *defined* on the
>> object to which it belongs (the order does not always exist)
>
> It has a perfectly valid and useful definition with a very mild assumption.

Most functions of this class that are not broken (contrary to
.base_ring, N, subs, ...) make this assumption. The class itself
should be changed. Even functions which *should* work (because of this
order) fail because the permutation contains zero:

sage: SetPartition([[0,1,2],[3,4]]).to_permutation()
...
ValueError: All elements should be strictly positive integers, and
I just found a negative one.

What you see is the result of long and careless programming: nobody
cared to check the assumptions of the functions they write, *AND* they
were all convinced that the functions only meant to handle the object
that they have in mind, i.e. SetPartition on 1,...,n.

You cannot "fix it" by adding some doc (even if you actually end up
doing it). You need to actively check the assumptions that the
functions make, or declare once and for all that this class is only
meant to handle the kind of input that Permutation does (1- indexed
again. Seriously ...).

> I don't mind adding a *little* warning to the doc.

Think of the users.

> BTW, the only messages complaining about this I've seen is from you.

Theorem: When the first person complains, he is the only one to complain.

Nathann

[Martin R]

Actually, I propose to delete all code from sage, because it doesn't work in all circumstances.

It might be useful for some people (not all that many), but we are actually doing them a favour because we save them from using software in circumstances where it doesn't apply.  Thus, by deleting sage, we will contribute to their happiness.

Moreover, we are going to save a lot of disk space and cpu time, that will then find much better use!

Martin

PS: more seriously: if you don't know what to_permutation does, why would you use it?

[Dima Pasechnik]

WTF? Permutation on a set is a just a bijection, isn't it?
And whoever coded and reviewed this crap cannot even tell 0 from a negative number, you know:

sage: s=SetPartition([[0,1,2],[3,4]])
sage: s.to_permutation()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

[Martin R]

Indeed, as I said, we should get rid of the Permutation class, because it is buggy.

Martin

[Dima Pasechnik]

ever heard of *bug fixing*, no?
 

Martin

[Martin R]

I tried to point out a possible improvement to the SetPartition code in http://trac.sagemath.org/ticket/19737, because I used this code.  I also provided a patch.

I was told that the original code is nonsensical.  I disagree.  In fact, from a recent experience with sage now disallowing empty rows in a tableau (which I used frequently),  I would rather prefer to change the docstring than raise an exception.  I'll do this on the ticket.

But I cannot fix the permutation class now.  That's way beyond my time budget.

Please excuse my sarcastic responses before.  I find it hard to deal with being told off when trying to contribute.

Martin

[Nathann Cohen]

Yooooooooo, 

Please excuse my sarcastic responses before.  I find it hard to deal with being told off when trying to contribute.

Don't take it bad, it is the same for all of us here. Wanna know how many tickets I opened just to give them up two days later, because people did not like them ? None of us has a write access that bypasses reviewer's advice.

Nathann