dimino.py

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)
    Géléments.discard(f)
    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:
    L.add(g)
    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))