SetPartition.to_permutation().cycle_tuples() is not the identity

[mantepse]

The docstring of SetPartition.to_permutation says:

Convert self to a permutation by considering the partitions as cycles.

However, I was very surprised to learn that it does not do this by sorting the blocks. That is, there is currently no guarantee that:

SetPartition([[1,2,3]]).to_permutation() == Permutation([2,3,1])

Since this caused some discomfort (I thought a conjecture I like a lot would be wrong...) I propose to change this behaviour.

The following looks reproducible:

p = SetPartition([(1, 9, 8), (2, 3, 4, 5, 6, 7)]); p.to_permutation().cycle_tuples()
[(1, 9, 8), (2, 3, 4, 5, 6, 7)]

Component: combinatorics

Keywords: set partitions, permutations

Author: Martin Rubey

Branch/Commit: dfc5666

Reviewer: Nathann Cohen

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

[mantepse]

Branch: u/mantepse/setpartition_to_permutation___cycle_tuples___is_not_the_identity

[mantepse]

Commit: 7d20d99

[nathanncohen]

comment:4

What on earth is this SetPartition.to_permutation function? How is it mathematically defined? O_o

[nathanncohen]

comment:5

Okay I see. Findstat.

[nathanncohen]

comment:6

I just wrote to sage-devel. I do not see how to_permutation can be properly defined on this class of objects. In particular it raises an exception whenever the ground set of the SetPartition object is not a set of integers.

https://groups.google.com/d/topic/sage-devel/OpwJoAza5OY/discussion

Nathann

[mantepse]

comment:7

Replying to @nathanncohen:

Okay I see. Findstat.

No, this has nothing to do with FindStat (except for both being about combinatorics).

[nathanncohen]

comment:8

A function which is named to_permutation and decorated from its origin with a combinatorial_map decorator? I say that's for FindStat. And you are free to not believe me :-P

[dimpase]

comment:9

sage: s=SetPartition([[0,1,2],[3,4]])
sage: s.to_permutation()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: All elements should be strictly positive integers, and I just found a negative one.

even 0 is negative in this code...

[sagetrac-git]

Changed commit from 7d20d99 to 26169d7

[sagetrac-git]

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

26169d7

clarify docstrings

[mantepse]

comment:11

Replying to @dimpase:

sage: s=SetPartition([[0,1,2],[3,4]])
sage: s.to_permutation()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: All elements should be strictly positive integers, and I just found a negative one.

even 0 is negative in this code...

Please open another ticket for this, since it is a problem with the Permutation code:

sage: Permutation(((0,1),))
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-22-0bc8d0916c3c> in <module>()
----> 1 Permutation(((Integer(0),Integer(1)),))

/home/martin/sage-master/src/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (/home/martin/sage-master/src/build/cythonized/sage/misc/classcall_metaclass.c:1239)()
    324         """
    325         if cls.classcall is not None:
--> 326             return cls.classcall(cls, *args, **kwds)
    327         else:
    328             # Fast version of type.__call__(cls, *args, **kwds)

/home/martin/sage-master/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in __classcall_private__(cls, l, check_input)
    530                 if isinstance(l[0], tuple):
    531                     n = max(max(x) for x in l)
--> 532                     return from_cycles(n, [list(x) for x in l])
    533                 else:
    534                     n = max(l)

/home/martin/sage-master/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in from_cycles(n, cycles, parent)
   6652     # Only positive elements
   6653     if int(flattened_and_sorted[0]) < 1:
-> 6654         raise ValueError("All elements should be strictly positive "
   6655                          "integers, and I just found a negative one.")
   6656 

ValueError: All elements should be strictly positive integers, and I just found a negative one.

[nathanncohen]

comment:13

The requirement is not that the ground set be totally ordered. The requirement is that the ground set should be {1,...,n}.

[mantepse]

comment:14

Replying to @nathanncohen:

The requirement is not that the ground set be totally ordered. The requirement is that the ground set should be {1,...,n}.

Oh, I missed that, I thought that Permutation would handle bijections, not just Permutations of {1,...,n}. That's really strange, I must say.

Hm, now I'm not sure what should be done. I guess, the only reasonable thing then is to fail when the ground set is not of this form. Well, that might make sense anyway.

[nathanncohen]

comment:15

Oh, I missed that, I thought that Permutation would handle bijections, not just Permutations of {1,...,n}. That's really strange, I must say.

Hm, now I'm not sure what should be done. I guess, the only reasonable thing then is to fail when the ground set is not of this form. Well, that might make sense anyway.

On the sage-devel thread I opened (se [comment:6]) I proposed to rename the class (or to create a new one) which checks from the start that its ground set is 1...n. This way, one could write methods like to_permutation without having to check it manually, each time.

There is a usage from a SetPartition class with arbitrary ground set (I do have examples in mind) and usage for a specific IntegerSetPartition class restricted to those 1...n integers, which is the only case many seem to be interested in.

Mixing the two, as it is done in this class, is a bad idea.

Nathann

[sagetrac-git]

Changed commit from 26169d7 to c6a3939

[sagetrac-git]

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

c6a3939

modify docstring to take into account that Permutation assumes 1,...,n as ground set.

[nathanncohen]

comment:17

A bit unrelated, but just for fun:

sage: X = map(GF(13),range(1,13))
sage: SetPartition([X])
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}}
sage: SetPartition([X]).to_permutation()
TypeError: 'sage.rings.finite_rings.integer_mod.IntegerMod_int' object is not iterable

[mantepse]

comment:18

Replying to @nathanncohen:

Oh, I missed that, I thought that Permutation would handle bijections, not just Permutations of {1,...,n}. That's really strange, I must say.

Hm, now I'm not sure what should be done. I guess, the only reasonable thing then is to fail when the ground set is not of this form. Well, that might make sense anyway.

On the sage-devel thread I opened (se [comment:6]) I proposed to rename the class (or to create a new one) which checks from the start that its ground set is 1...n. This way, one could write methods like to_permutation without having to check it manually, each time.

There is a usage from a SetPartition class with arbitrary ground set (I do have examples in mind) and usage for a specific IntegerSetPartition class restricted to those 1...n integers, which is the only case many seem to be interested in.

Mixing the two, as it is done in this class, is a bad idea.

I am not quite convinced that this is true. But if you are convinced, is there an easy way to do it? Can I simply do

class IntegerSetPartition(SetPartition):

    def to_permutation(self):
        ....

where should I put the check that the ground set is {1,...,n}?

[nathanncohen]

comment:19

Hello,

I am not quite convinced that this is true. But if you are convinced, is there an easy way to do it? Can I simply do

class IntegerSetPartition(SetPartition):

    def to_permutation(self):
        ....

To me such a design would work nicely. And the check that is needed by all those functions can be performed there:

class IntegerSetPartition(SetPartition):
    def __init__(self, **kwargs):
        SetPartition.__init__(self,**kwargs)
        assert set(self.base_set()) == set(range(self.base_set_cardinality()))

Or something nicer, which would yield a clearer error message when the input is wrong.

I believe that this is the way to go. Really, look at the functions of SetPartition: how many are defined for integer partitions only? I don't know much about this kind of combinatorics, but is_noncrossing seems to be of that kind. Hell, I'd even be surprised if less than half of the methods of SetPartition should not be there, or is plain broken (.N(), .base_extend(), .base_ring(), .count(), db(), .n(), .numerical_approx(), .rename(), .reset_name(), .subs(), .substitute(), .version()).

Nathann

[mantepse]

comment:20

I just tried exactly what you suggested, but it does not work:

sage: IntegerSetPartition([[1,2],[3]])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-406bd8f08b79> in <module>()
----> 1 IntegerSetPartition([[Integer(1),Integer(2)],[Integer(3)]])

/home/martin/sage-master/src/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (/home/martin/sage-master/src/build/cythonized/sage/misc/classcall_metaclass.c:1264)()
    327         else:
    328             # Fast version of type.__call__(cls, *args, **kwds)
--> 329             return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    330 
    331     def __get__(cls, instance, owner):

TypeError: __init__() takes exactly 1 argument (2 given)

I'm guessing this is because SetPartition uses __metaclass__ = InheritComparisonClasscallMetaclass, whatever that is.

Also, I have to remark that none of .N(), .base_extend(), .base_ring(), .count(), db(), .n(), .numerical_approx(), .rename(), .reset_name(), .subs(), .substitute(), .version()) are defined in SetPartition. Eg., .N() is from Element.

[mantepse]

comment:21

I half-got it, but it looks more complicated. Apparently, it is not possible to use the same parent. Currently, there is a parent SetPartitions with element class SetPartition. Of course, it would be desirable to make an instance of IntegerSetPartition also have parent SetPartitions, but I do not know how to do this yet.

[mantepse]

comment:22

OK, I think I have it.

[mantepse]

comment:23

I now put

class IntegerSetPartition(SetPartition):

    def __init__(self, parts):
        SetPartition.__init__(self, SetPartitions(), parts)
        assert set(self.base_set()) == set(range(1, 1+self.base_set_cardinality()))

    def to_permutation(self):
    ...

but that's not really satisfying. What we really want is that SetPartition([[1,2],[3]]) creates an IntegerSetPartition. I hate python.

[nathanncohen]

comment:24

HMmmmmmmmm O_o

That seems hard to achieve indeed. The only way I've seen those things done in combinat/ code is to make SetPartition a function, which then calls SetPartition_class or IntegerSetPartition_class. Can't say I am in love with that design, though.

Nathann

[mantepse]

comment:25

OK, then I would suggest to just have the easy fix. At least it's less surprising than what we currently have.

Turning SetPartition into a function would really be a completely new design. Out of curiosity: why would you dislike this solution, too?

[nathanncohen]

comment:26

Turning SetPartition into a function would really be a completely new design. Out of curiosity: why would you dislike this solution, too?

Because I love simple things. From time to time I have to touch combinat code, and from time to time I have to use 'isinstance'. And, well, isinstance(my_object,IncidenceStructure) works but isinstance(my_object,Poset) does not, because the first is a class while the other is not.

Usually in Sage we have a way to tell whether something is a function or a class: MyClass is a class, and my_function is a function.

But well, what is true in Sage and what is true in the combinat/ folder are different things.

Nathann

[mantepse]

comment:27

Well, that's why I hate python. A better solution (in my opinion) would be to have conditionally exported methods. Or, lacking this, the possibility to have a function and a class of the same name, eg., SetPartition would be a function that return an instance of a class of the same name, or an instance of IntegerSetPartition.

In fact, that's sort of doable, but it seems to involve a fair bit of work: I can have a class that is simultaneously a function, using __classcall_private__. And it seems to be working hard against python.

Can you give this ticket positive review now?

[nathanncohen]

comment:28

Well, that's why I hate python.

You hate Python because the combinat folks break name conventions? O_o

A better solution (in my opinion) would be to have conditionally exported methods.

What do you mean by that? Can you give an example?

Or, lacking this, the possibility to have a function and a class of the same name, eg., SetPartition would be a function that return an instance of a class of the same name, or an instance of IntegerSetPartition.

That's what I call making things complicated. Can't people live with classes that return instances of themselves?

Can you give this ticket positive review now?

I added a small commit at public/19737. If you agree with it, please add it to this ticket and set the status to positive_review.

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[mantepse]

comment:29

No, I hate python because, in my opinion, it lacks a lot of functionality and it is very complicated at the same time.

For example, in Aldor I can simply say: if the parameters are the integers from 1 to n, then export the method "to_permutation" (i.e., make it visible to the user). Otherwise, do not export this method.

Or, lacking this, the possibility to have a function and a class of the same name, eg., SetPartition would be a function that return an instance of a class of the same name, or an instance of IntegerSetPartition.

That's what I call making things complicated. Can't people live with classes that return instances of themselves?

OK, but you said you don't like SetPartition having methods that do not apply to all its instances. Or would you prefer to type IntegerSetPartition all the time, and make SetPartition([[1]]) and IntegerSetPartition([[1]]) different objects?

I added a small commit at public/19737. If you agree with it, please add it to this ticket and set the status to positive_review.

I do not have proper access to git from this computer. Your change is of course OK, so if you don't want to wait until tomorrow, please merge and set it to positive review.

Thanks!

[nathanncohen]

Changed branch from u/mantepse/setpartition_to_permutation___cycle_tuples___is_not_the_identity to public/19737

[nathanncohen]

comment:30

Hellooooo,

For example, in Aldor I can simply say: if the parameters are the integers from 1 to n, then export the method "to_permutation" (i.e., make it visible to the user). Otherwise, do not export this method.

Sounds hard to write documentation for something like that. To me it sounds like the other approach "Have every method available, but check that the data is what you expect before running the computation and raise a clear error message if it is not".

You would have all methods available, some of which would raise an exception. Not ideal, but at least you don't wonder where the method is. Well, this being said I can totally hear that when one is used to this behaviour, one expects this kind of situation too.

OK, but you said you don't like SetPartition having methods that do not apply to all its instances. Or would you prefer to type IntegerSetPartition all the time, and make SetPartition([[1]]) and IntegerSetPartition([[1]]) different objects?

That's indeed how I would have implemented it. Two classes, one which inherits from the other.

I do not have proper access to git from this computer. Your change is of course OK, so if you don't want to wait until tomorrow, please merge and set it to positive review.

Done!

Thanks,

Nathann

---

New commits:

99e8d5f	trac #19737: Merged with 7.0.beta3
dfc5666	trac #19737: LaTeX formatting

[nathanncohen]

Changed commit from c6a3939 to dfc5666

[vbraun]

Changed branch from public/19737 to dfc5666