Opened 2 years ago
Last modified 2 months ago
#28653 needs_work enhancement
Faster iterator for permutation groups
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  group theory  Keywords:  
Cc:  slelievre  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/ticket28653 (Commits, GitHub, GitLab)  Commit:  78088d9dffc46835743683937e22f0e438fd871b 
Dependencies:  Stopgaps: 
Description (last modified by )
The default iterator for permutation group makes use of a strong generating system (when the group is not cyclic). This is expensive and should be avoided for faster code when the group is well known or small. However, as noticed in #28539, the RecursiveEnumeratedSet
generates elements in a different order in Python 2 and Python 3 and makes it delicate to use.
For some named permutation groups (symmetric, alternating, dihedral) we implement direct straightforward algorithms.
Change History (23)
comment:1 Changed 23 months ago by
 Description modified (diff)
comment:2 Changed 21 months ago by
 Milestone changed from sage9.0 to sage9.1
comment:3 Changed 18 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:4 Changed 13 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:5 Changed 13 months ago by
 Cc slelievre added
Different order in Python 2 and Python 3 is no longer be a problem.
comment:6 Changed 12 months ago by
 Branch set to public/ticket28563
 Commit set to 126c5d775c2d5ce47f9fdfc6cf39d4317650def6
voila une premiere tentative naive. Pas bien plus rapide, en fait
New commits:
126c5d7  specific iterators for SymmetricGroup and AlternatingGroup

comment:7 Changed 12 months ago by
 Commit changed from 126c5d775c2d5ce47f9fdfc6cf39d4317650def6 to ac936ffb29bbf70d4160574da594fb3f680145fa
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ac936ff  specific iterators for SymmetricGroup and AlternatingGroup

comment:8 Changed 12 months ago by
 Commit changed from ac936ffb29bbf70d4160574da594fb3f680145fa to 2a136b4bca17746bbd9d8b4cb5d615b45107c43a
Branch pushed to git repo; I updated commit sha1. New commits:
2a136b4  better iterator for AlternatingGroup

comment:9 Changed 12 months ago by
 Branch changed from public/ticket28563 to public/ticket28653
 Status changed from new to needs_info
is this reasonable now ?
comment:10 Changed 12 months ago by
What I thought was to reuse sage.combinat.permutation_cython.pyx
. But in this module, it was decided to use unsigned int
whereas PermutationGroupElement
uses int
. This is quite unfortunate.
If you use the swap algorithm from Knuth, it is trivial to make it work for A_n
since permutations are alternatively even and odd (two neighboring permutations in the iterator differs by a transposition).
comment:11 Changed 10 months ago by
 Dependencies #28652 deleted
 Status changed from needs_info to needs_review
Voila une nouvelle tentative.
comment:12 Changed 10 months ago by
 Commit changed from 2a136b4bca17746bbd9d8b4cb5d615b45107c43a to e4d5636b98aa166ba9d9fe8c68a434563a149702
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e4d5636  specific iterators for SymmetricGroup and AlternatingGroup

comment:13 Changed 10 months ago by
 Commit changed from e4d5636b98aa166ba9d9fe8c68a434563a149702 to 85f9a1472fea03aa6ecd0bfb2b62aff29db477ef
Branch pushed to git repo; I updated commit sha1. New commits:
85f9a14  fix for symmetric group

comment:14 Changed 10 months ago by
 Commit changed from 85f9a1472fea03aa6ecd0bfb2b62aff29db477ef to 07c3969d2ab94d081aeec61292501e5e6d4b54c0
Branch pushed to git repo; I updated commit sha1. New commits:
07c3969  fix doctest

comment:15 Changed 10 months ago by
 Description modified (diff)
comment:16 Changed 10 months ago by
 Commit changed from 07c3969d2ab94d081aeec61292501e5e6d4b54c0 to 78088d9dffc46835743683937e22f0e438fd871b
Branch pushed to git repo; I updated commit sha1. New commits:
78088d9  Merge branch 'public/ticket28653' in 9.3.b3

comment:17 Changed 10 months ago by
bon, alors evidemment, ca casse un certain nombre de doctests. Avant de se lancer dans l'etude au cas par cas de ces doctests, je voudrais savoir si le code proposé est une bonne idée ou pas.
En particulier, pour les permutations, vautil mieux passer par itertools comme je le fait ou bien faire la meme chose que pour les permutations alternées ?
peutetre aussi peuton utiliser une maniere plus efficace de créer une permutation ?
comment:18 Changed 10 months ago by
Les permutations sont des tableaux d'entiers en C. Voir comment:10.
comment:19 Changed 10 months ago by
Certes. Mais tu veux dire quoi, exactement ? Qu'il faut réimplementer l'algo de Knuth au lieu d'utiliser la version existante, qui ne se passe pas au niveau array ?
comment:20 Changed 10 months ago by
Qu'il faut réécrire les fonctions de sage/combinat/permutation_cython.pyx
de manière à ce qu'elles soient aussi utilisables par PermutationGroupElement
.
comment:21 Changed 7 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:22 Changed 5 months ago by
 Status changed from needs_review to needs_work
There are multiple failing tests.
comment:23 Changed 2 months ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
Ticket retargeted after milestone closed