Itération de compositions (permutation-cycle)

def my_cycles_perm(sigma):
    ss=sigma
    s=deepcopy(ss)
    l=len(ss) # Longueur de sigma
    c=range(l)
    p=[] # Je commence par une liste vide
    pp=[[p]] # Liste de mes cycles
    for i in (c): # Je cherche la position i dans c qui me donne une valeur qui n'est pas encore dans p
        lp=len(p)
        j=0
        while j<lp:
            if i==p[j]:
                j=j+1
            else: # Une fois que j'ai trouvé une valeur i qui n'est pas encore dans un cycle p, je regarde ce que donne i par sigma
                while i<l:
                    r=s[i-1] # Car SAGE commence à compter de 0
                    p.append(r) # Je rajoute cette valeur trouvée dans ma liste
                    if r!=(i): # Si l'image est différent de la position, je regarde l'image de l'image
                        r=s[r]
                        p.append(r) # Je rajoute la nouvelle valeur dans ma liste
                    else:
                        print(p)

Math Cross a écrit:

Cette liste est destinée à accumuler quoi ? Un cycle ? des cycles ?
Ne serait-il pas plus clair d'avoir une liste qui contient tous les cycles calculés jusque là et une liste temporaire qui contient le cycle en train de se construire ?

Math Cross a écrit:

Jusqu'à quand ? Tu vas traduire ça par une condition d'arrêt qui porte sur quelle(s) variable(s) ?

                while i<l:
                    r=s[i-1] # Car SAGE commence à compter de 0
                    p.append(r) # Je rajoute cette valeur trouvée dans ma liste
                    if r!=(i): # Si l'image est différent de la position, je regarde l'image de l'image
                        r=s[r-1]
                        p.append(r) # Je rajoute la nouvelle valeur dans ma liste
                    else:
                        print(p)

    for i in (c): # Je cherche la position i dans c qui me donne une valeur qui n'est pas encore dans p
        lp=len(p)
        j=0
        while j<lp:
            if i==p[j]:
                j=j+1
            else: # Une fois que j'ai trouvé une valeur i qui n'est pas encore dans un cycle p, je regarde ce que donne i

Math Cross a écrit:

Avant de faire une fonction qui décompose en cycle, pourrais-tu décrire un algorithme (ça veut dire qu'il faut expliciter les boucles sous forme "for ..." ou "while..." et surtout toutes les variables) correspondant au sous-problème suivant :

# Soit list une liste, je cherche une liste d'entiers tous différents de 1 au nombre d'éléments de la liste
a=len(list)
b=range(2,a)
# k = un entier entre 1 et le nombre d'éléments de sigma
r=range(1,a)
for r in c:

def cycle(sigma,k):
    ss=sigma
    s=deepcopy(ss)
    p=[]
    r=s[k-1]
    if r!=k:
        p.append(k)
        while r!=k:
            p.append(r)
            r=s[r-1]
    return(p)

def my_cycles_perm(sigma):
    ss=sigma
    s=deepcopy(ss)
    l=len(ss)
    p=[]                      # On commence par une liste vide
    k=1                        
    while k<l:
        yy=cycle(sigma,k)     # On veut le cycle de permutations pour k
        if p==[]:             # Si on au départ, la liste est vide, on rajoute le cycle précédent
            p.append(yy)
        if p!=[]:             # Si c'est non vide, il faut d'abord vérifier que le cycle n'est pas déjà dans p
            y=Set(yy)         # On utilise la fonction Set pour ne vérifier que les éléments dans les listes
            ll=len(p)
            c=range(ll)
            i=0               # On commence par vérifier pour le premier élément de la liste des listes de p
            ens=Set(p[ i])    # On définit les ensembles des listes dans p
            last=Set(p[ll-1]) # On appelle last, le dernier ensemble dans la liste des listes de p
            if y!=ens:        # Et si y est différent d'un ensemble de la liste p,
                while i<ll:   # Tant que i est plus petit que la longueur de la liste p
                    i=i+1     # on passe à la vérification de l'élément suivant, (sinon on fait k=k+1)
                    if y!=last: # Si après vérification de tous les i, à chaque fois c'est différent, on arrive au dernier élément de la liste p et que c'est différent, alors on l'ajoute dans p
                        p.append(yy)
        k=k+1
    return(p)