Opened 5 years ago

Closed 5 years ago

#21069 closed defect (fixed)

comparison of permutation and standard permutation

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-7.5
Component: coercion Keywords:
Cc: sage-combinat, darij, nthiery, SimonKing Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: dc5c35a (Commits, GitHub, GitLab) Commit: dc5c35a14ab8a06d82980b901057f7b2a7257649
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

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).

Change History (20)

comment:1 follow-up: Changed 5 years ago by tscrim

  • Cc sage-combinat darij added

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.

comment:2 in reply to: ↑ 1 Changed 5 years ago by dkrenn

  • Milestone changed from sage-7.3 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

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.

comment:3 Changed 5 years ago by dkrenn

  • Status changed from needs_review to positive_review

Set to invalid.

comment:4 follow-up: Changed 5 years ago by tscrim

  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.4
  • Status changed from positive_review to needs_work
  • Summary changed from comparison of permutation and list: unexpected result to comparison of permutation and standard permutation

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

comment:5 in reply to: ↑ 4 Changed 5 years ago by dkrenn

Replying to tscrim:

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

Ok.

comment:6 Changed 5 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/combinat/partitions_std_set-21069
  • Commit set to 01963652a467b29bf94cf4eb74c92779775d7441
  • Status changed from needs_work to needs_review

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


New commits:

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

comment:7 Changed 5 years ago by tscrim

  • Branch changed from public/combinat/partitions_std_set-21069 to public/combinat/permutations_std_set-21069

I just realized the branch is named wrong...

comment:8 Changed 5 years ago by git

  • Commit changed from 01963652a467b29bf94cf4eb74c92779775d7441 to 7548e6e8cfbeb0983133edfe6ec712dae3b7415a

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

14b364eMerge branch 'public/combinat/permutations_std_set-21069' in 7.4.b1
7548e6etrac 21069 fixing a doctest in Dyck words

comment:9 Changed 5 years ago by darij

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

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

comment:10 Changed 5 years ago by tscrim

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

comment:11 Changed 5 years ago by darij

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

comment:12 follow-up: Changed 5 years ago by darij

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?
  1. 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?

comment:13 in reply to: ↑ 12 Changed 5 years ago by tscrim

Replying to darij:

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.

  1. 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.

comment:14 follow-up: Changed 5 years ago by darij

  1. OK.
  1. 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.

comment:15 in reply to: ↑ 14 Changed 5 years ago by tscrim

Replying to darij:

  1. 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.

comment:16 Changed 5 years ago by darij

  • Cc nthiery SimonKing added

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?

comment:17 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

2 failing doctests, see bot

comment:18 Changed 5 years ago by git

  • Commit changed from 7548e6e8cfbeb0983133edfe6ec712dae3b7415a to dc5c35a14ab8a06d82980b901057f7b2a7257649

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

3cc7873Merge branch 'public/combinat/permutations_std_set-21069' of git://trac.sagemath.org/sage into public/combinat/permutations_std_set-21069
dc5c35aChange due to Python3 list.

comment:19 Changed 5 years ago by tscrim

  • Milestone changed from sage-7.4 to sage-7.5
  • Reviewers set to Darij Grinberg
  • Status changed from needs_work to positive_review

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.

comment:20 Changed 5 years ago by vbraun

  • Branch changed from public/combinat/permutations_std_set-21069 to dc5c35a14ab8a06d82980b901057f7b2a7257649
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.