Faster iterator for permutation groups

[videlec]

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.

CC: @slel

Component: group theory

Author: Vincent Delecroix

Branch/Commit: public/ticket-28653 @ 78088d9

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

[embray]

comment:2

Ticket retargeted after milestone closed

[mkoeppe]

comment:3

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.

[slel]

comment:5

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

[fchapoton]

comment:6

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

---

New commits:

126c5d7

specific iterators for SymmetricGroup and AlternatingGroup

[fchapoton]

Commit: 126c5d7

[fchapoton]

Branch: public/ticket-28563

[sagetrac-git]

Changed commit from 126c5d7 to ac936ff

[sagetrac-git]

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

ac936ff

specific iterators for SymmetricGroup and AlternatingGroup

[sagetrac-git]

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

2a136b4

better iterator for AlternatingGroup

[sagetrac-git]

Changed commit from ac936ff to 2a136b4

[fchapoton]

Changed branch from public/ticket-28563 to public/ticket-28653

[fchapoton]

comment:9

is this reasonable now ?

[videlec]

comment:10

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

[fchapoton]

comment:11

Voila une nouvelle tentative.

[fchapoton]

Changed dependencies from #28652 to none

[sagetrac-git]

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

e4d5636

specific iterators for SymmetricGroup and AlternatingGroup

[sagetrac-git]

Changed commit from 2a136b4 to e4d5636

[sagetrac-git]

Changed commit from e4d5636 to 85f9a14

[sagetrac-git]

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

85f9a14

fix for symmetric group

[sagetrac-git]

Changed commit from 85f9a14 to 07c3969

[sagetrac-git]

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

07c3969

fix doctest

[sagetrac-git]

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

78088d9

Merge branch 'public/ticket-28653' in 9.3.b3

[sagetrac-git]

Changed commit from 07c3969 to 78088d9

[fchapoton]

comment:17

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 ?

[videlec]

comment:18

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

[fchapoton]

comment:19

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 ?

[videlec]

comment:20

Qu'il faut réécrire les fonctions de sage/combinat/permutation_cython.pyx de manière à ce qu'elles soient aussi utilisables par PermutationGroupElement.

[mkoeppe]

comment:21

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

[roed314]

comment:22

There are multiple failing tests.

[mkoeppe]

comment:23

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