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: sage-9.5
Component: group theory Keywords:
Cc: slelievre Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: public/ticket-28653 (Commits, GitHub, GitLab) Commit: 78088d9dffc46835743683937e22f0e438fd871b
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

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 vdelecroix

  • Description modified (diff)

comment:2 Changed 21 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:3 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:5 Changed 13 months ago by slelievre

  • Cc slelievre added

Different order in Python 2 and Python 3 is no longer be a problem.

comment:6 Changed 12 months ago by chapoton

  • Branch set to public/ticket-28563
  • Commit set to 126c5d775c2d5ce47f9fdfc6cf39d4317650def6

voila une premiere tentative naive. Pas bien plus rapide, en fait


New commits:

126c5d7specific iterators for SymmetricGroup and AlternatingGroup

comment:7 Changed 12 months ago by git

  • Commit changed from 126c5d775c2d5ce47f9fdfc6cf39d4317650def6 to ac936ffb29bbf70d4160574da594fb3f680145fa

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ac936ffspecific iterators for SymmetricGroup and AlternatingGroup

comment:8 Changed 12 months ago by git

  • Commit changed from ac936ffb29bbf70d4160574da594fb3f680145fa to 2a136b4bca17746bbd9d8b4cb5d615b45107c43a

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

2a136b4better iterator for AlternatingGroup

comment:9 Changed 12 months ago by chapoton

  • Branch changed from public/ticket-28563 to public/ticket-28653
  • Status changed from new to needs_info

is this reasonable now ?

comment:10 Changed 12 months ago by vdelecroix

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 chapoton

  • Dependencies #28652 deleted
  • Status changed from needs_info to needs_review

Voila une nouvelle tentative.

comment:12 Changed 10 months ago by git

  • Commit changed from 2a136b4bca17746bbd9d8b4cb5d615b45107c43a to e4d5636b98aa166ba9d9fe8c68a434563a149702

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e4d5636specific iterators for SymmetricGroup and AlternatingGroup

comment:13 Changed 10 months ago by git

  • Commit changed from e4d5636b98aa166ba9d9fe8c68a434563a149702 to 85f9a1472fea03aa6ecd0bfb2b62aff29db477ef

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

85f9a14fix for symmetric group

comment:14 Changed 10 months ago by git

  • Commit changed from 85f9a1472fea03aa6ecd0bfb2b62aff29db477ef to 07c3969d2ab94d081aeec61292501e5e6d4b54c0

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

07c3969fix doctest

comment:15 Changed 10 months ago by slelievre

  • Description modified (diff)

comment:16 Changed 10 months ago by git

  • Commit changed from 07c3969d2ab94d081aeec61292501e5e6d4b54c0 to 78088d9dffc46835743683937e22f0e438fd871b

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

78088d9Merge branch 'public/ticket-28653' in 9.3.b3

comment:17 Changed 10 months ago by chapoton

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, vaut-il mieux passer par itertools comme je le fait ou bien faire la meme chose que pour les permutations alternées ?

peut-etre aussi peut-on utiliser une maniere plus efficace de créer une permutation ?

comment:18 Changed 10 months ago by vdelecroix

Les permutations sont des tableaux d'entiers en C. Voir comment:10.

comment:19 Changed 10 months ago by chapoton

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 vdelecroix

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 mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:22 Changed 5 months ago by roed

  • Status changed from needs_review to needs_work

There are multiple failing tests.

comment:23 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

Setting a new milestone for this ticket based on a cursory review.

Note: See TracTickets for help on using tickets.