permutations.py

Created on May 28, 2018

552 Bytes

Calcule le produit de permutations comme (1 2)(1 3 2) et qui vaut (1 3). usage : permutations(“(1 2)(1 3 2)”) If you want to calculate a power of a permutation, do permutations(“(1 6 4 3)(2 5)(7 8 10)”*5).

def permutations(s):
 p=s[1:-1].split(")(")
 pp=[list(map(int,l.split())) for l in p][::-1]
 p=[]
 for l in pp:
  if l:
   p+=[l+[l[0]]]
 if not p:
  p=[[1,1]]
 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={i:0 for i in range(1,m+1)}
 r=[]

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

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