Combinatoire

Combinatoire

## Permutations d'une liste

from copy import deepcopy

def rotation(l,k):
    """
    Renvoie la liste l avec une rotation à partir de l'indice k
    """
    m=deepcopy(l)
    m.append(l[k])
    del m[k]
    return m

def liste_rotations(l,k):
    """
    Calcule la liste de toutes les rotations possibles successives de la liste l à partir de l'indice k
    """
    rot=[l]
    u=deepcopy(l)
    n=len(l)
    for i in range(0,n-k-1):
        u=rotation(u,k)
        rot.append(u)
    return rot

def permutations(l):
    """
    Calcule la liste de toutes les permutations de la liste l
    """
    perm=[l]
    n=len(l)
    for k in range(0,n-1):
        for i in range(0,len(perm)):
            liste_rot=liste_rotations(perm[i],k)
            for p in liste_rot:
                if not (p in perm):
                    perm.append(p)
    return(perm)

## Powerset 

def powerset(l):
    """
    Calcule l'ensemble des parties de la liste l
    """
    if l == []:
        return [[]]
    else:
        elem=l[0]
        reste=l[1:]
        parties_reste  = powerset(reste)
        parties = []
        for p in parties_reste:
            parties.append(p)
            parties.append(p+[elem])
        return parties

# Exemple : calcul des parties de [1,2,3]
# 
# element = 1
# reste = [2,3]
# 
#     Calcul des parties de [2,3]
#     element = 2
#     reste = [3]
#     
#         Calcul des parties de [3]
#         element = 3
#         reste []
#         powerset_reste = [[]]
#         powerset_element = [[3]]
#         
#     powerset_reste = [[],[3]]
#     powerset_element = [[2],[2,3]]
#     
# powerset_reste = [[],[2],[3],[2,3]]
# powerset_element = [[1],[1,2],[1,3],[1,2,3]]
# 
# 
# resultat = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]

## Combinaisons 

def combinaison(l,p):
    """
    Calcule la liste des combinaisons possibles de p elemtents parmi ceux de l
    """
    return [part for part in powerset(l) if len(part)==p]

def combinaison2(l,p):
    """
    Meme chose, sans comprehension
    """
    pow = powerset(l)
    combi=[]
    for set in pow:
        if (len(set)==p):
            combi.append(set)    
    return combi

## Arrangements

def arrangement(l,p):
    """
    Calcule la liste des p-arrangements d'element de l
    """
    combi=combinaison(l,p)
    arr=[]
    for set in combi:
        arr = arr + permutations(set)
    return arr