comparison of permutation and standard permutation

[dkrenn]

Because ClonableArray also takes the parent into consideration of equality checking, we currently have the following:

sage: Permutations([1])[0] == Permutation([1])
False

I propose to have Permutations(range(n)) be identical to Permutations(n).

CC: @sagetrac-sage-combinat @darijgr @nthiery @simon-king-jena

Component: coercion

Author: Travis Scrimshaw

Branch/Commit: dc5c35a

Reviewer: Darij Grinberg

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

[tscrim]

comment:1

I think this is more an issue with the default _cmp_ in ClonableArray wanting to have a common parent, but there are not coercions between most combinatorial objects (nor should there be typically). IMO, this is even worse:

sage: Permutations([1])[0] == Permutation([1])
False

However, I don't agree with the argument that "same representation => equality". Should the partition [2, 1] equal the permutation [2, 1]? (Currently they do, but I think that is a small issue and you should not rely on this behavior.) We run into a major notation problem as there is not enough valid syntax and math notation to separate the two clearly; context (or their parents) separate them.

[dkrenn]

comment:2

Replying to @tscrim:

However, I don't agree with the argument that "same representation => equality". Should the partition [2, 1] equal the permutation [2, 1]? (Currently they do, but I think that is a small issue and you should not rely on this behavior.) We run into a major notation problem as there is not enough valid syntax and math notation to separate the two clearly; context (or their parents) separate them.

Ok, I agree.

[dkrenn]

comment:3

Set to invalid.

[tscrim]

comment:4

I am going to recycle this ticket to address the issue above.

[dkrenn]

comment:5

Replying to @tscrim:

I am going to recycle this ticket to address the issue above.

Ok.

[tscrim]

comment:6

While I was at it, I fixed the Permutations_nk.random_element, which was returning elements of [0, ..., n-1].

---

New commits:

0196365

Making permutations [1,...,n] be standard.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Branch: public/combinat/partitions_std_set-21069

[tscrim]

Commit: 0196365

[tscrim]

comment:7

I just realized the branch is named wrong...

[tscrim]

Changed branch from public/combinat/partitions_std_set-21069 to public/combinat/permutations_std_set-21069

[sagetrac-git]

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

14b364e	Merge branch 'public/combinat/permutations_std_set-21069' in 7.4.b1
7548e6e	trac 21069 fixing a doctest in Dyck words

[sagetrac-git]

Changed commit from 0196365 to 7548e6e

[darijgr]

comment:9

+                    if list(n) == range(1, len(n)+1):

Maybe you want sorted(n) rather than list(n) here?

[tscrim]

comment:10

No, I want list(n) because the identity permutations are different.

[darijgr]

comment:11

Oh, the word "permutation" is meant in the non-algebraic meaning! Makes sense then. Will look at the rest of the code now.

[darijgr]

comment:12

OK. Two issues:

1. Instances of class Permutations_set have a _set attribute, whereas objects of class StandardPermutations_n don't. Could this break things?

2. Is the time to call StandardPermutations_n higher than for Permutations_set? (I suspect it is, if only due to things like cat = FiniteWeylGroups().Irreducible() & FinitePermutationGroups().) Is this relevant?

[tscrim]

comment:13

Replying to @darijgr:

OK. Two issues:

1. Instances of class Permutations_set have a _set attribute, whereas objects of class StandardPermutations_n don't. Could this break things?

No because nobody should be using _set (nor do we have to respect it) because it is hidden.

2. Is the time to call StandardPermutations_n higher than for Permutations_set? (I suspect it is, if only due to things like cat = FiniteWeylGroups().Irreducible() & FinitePermutationGroups().) Is this relevant?

I don't understand what you're asking. If you're saying putting StandardPermutations_n as a superclass of Permutations_set, then we should not do that. It is too much of a can of worms and far outside the scope of this ticket.

[darijgr]

comment:14

1. OK.

2. What I mean is that calling Permutations([1,2,3]) might now suddenly be taking a lot longer. I don't know whether this is an actual issue because (a) I haven't tested, and (b) it is a parent, and maybe calling many parents is not a standard use case we should be optimizing for anyway. But I'm asking to be sure.

[tscrim]

comment:15

Replying to @darijgr:

2. What I mean is that calling Permutations([1,2,3]) might now suddenly be taking a lot longer. I don't know whether this is an actual issue because (a) I haven't tested, and (b) it is a parent, and maybe calling many parents is not a standard use case we should be optimizing for anyway. But I'm asking to be sure.

There are already such tests, so it really should not unless you're constantly doing things like [1,2,...,n,'a']. I also doubt it would be the bottleneck in a loop.

[darijgr]

comment:16

OK, the slowdown is in the single-digit percentages (just checked). The code LGTM then. To be safe, what do the guardians of the object hierarchy think about it?

[fchapoton]

comment:17

2 failing doctests, see bot

[sagetrac-git]

Changed commit from 7548e6e to dc5c35a

[sagetrac-git]

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

3cc7873	Merge branch 'public/combinat/permutations_std_set-21069' of git://trac.sagemath.org/sage into public/combinat/permutations_std_set-21069
dc5c35a	Change due to Python3 list.

[tscrim]

Reviewer: Darij Grinberg

[tscrim]

comment:19

Failure was due to me not using Python3-style list. Fixed and doctests now pass.

Since there were no comments from Darij's request in comment:16, I'm allowing myself to set this to a positive review.

[vbraun]

Changed branch from public/combinat/permutations_std_set-21069 to dc5c35a