# dimino.py

Created by nicolas-patrois

Created on May 23, 2021

2.35 KB

Dimino’s algorithm to find the order of a permutation subgroup.

```# Type your text here#!/usr/bin/python3

# e: identity operator
# G: list of generators
# L: list of all the elements of the group
# N: maximum order of the group we deem acceptable

def prod(chaine):
"""Calcule le produit de deux permutations
sous la forme minimale lexicographique
"""

p=chaine.replace("()","")[1:-1].split(")(")
p=[[int(i) for i in l.split()] for l in p][::-1]
p=[l+[l[0]] for l in p]
m=max(max(l) for l in p)
d={i:i for i in range(1,m+1)}

for e in range(1,m+1):
ee=e
for l in p:
if ee in l:
ee=l[l.index(ee)+1]
d[e]=ee

s=set(range(1,m+1))
r=[]

while s:
n=[]
e=min(s)
while e not in n:
s-={e}
n.append(e)
e=d[e]
if len(n)>1:
r.append(str(tuple(n)).replace(",",""))

if r:
return "".join(r)
return "()"

def réduction(G):
"""Réduit un ensemble de permutations
("(1 5 7 8 99)","(1 99 13 72)") devient ("(1 2 3 4 7)","(1 7 5 6)")
"""

Gprime=", ".join(G).replace("(","( ").replace(")"," ) ")
Gprime=Gprime.split()
Géléments=set(Gprime)-{")","(",","}
Grange=list(range(1,len(Géléments)+1))
while Grange:
e=Grange.pop(0)
f=min(Géléments)
while f in Gprime:
Gprime[Gprime.index(f)]=e
return tuple(map(prod," ".join(map(str,Gprime)).replace("( ","(").replace(" )",")").replace(") (",")(").split(" , ")))

def dimino(G=("(1 2)","(1 3)"),r=True):
"""Algorithme de Dimino pour déterminer
un groupe de permutations à l’aide de générateurs
r réduit la taille du groupe
"""
if r:
G=réduction(G)
e="()"
g=g1=G[0]
L={e}
while g != e:
g=prod(g+g1)

for i in range(1,len(G)):
C=[e]
L1=set(L)
more=True
while more:
more=False
for g in C[:]:
for s in G[:i+1]:
sg=prod(s+g)
if sg not in L:
C.append(sg)
L|={prod(sg+t) for t in L1}
more=True
"""print(i)
print(L)
print(C)"""
return len(L)

#print(prod("(1 2)()"))

#G=("(1 2)","(1 3)","(4 5)") # D6
#G=("(1 2 4 7)(3 6 8 5)","(1 3 4 8)(2 5 7 6)") # Quaternions
#G=("(1 2 3 4 7)","(1 7 5 6)") # S_7 rapide
G=("(1 5 7 8 99)","(1 99 13 72)") # S_7 lent
G=("(1 2 3)","(1 4 5)") # A_5
G=("(1 3 6 5 4 8 7 2)","(3 7 1)(4 8 6)") # Gl_2(F_3)
#G=("(1 6 4 7)(3 5 8 2)","(1 3 7)(4 8 6)") # Sl_2(F_3)

#print(dimino(G,True))```