UPLETS

1 - Exemples et opérations élémentaires


?

>>> u = (1, 2, 3)
>>> len(u)
3
>>> u[0]
1

>>> tuple(range(1, 10+1))
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

>>> list( (1, 2, 3) )
[1, 2, 3]
>>> tuple( [1, 2, 3] )
(1, 2, 3)

>>> u = (1, 2, 3)
>>> u[0] = -1
Error: 'tuple' object does not support item assignment

>>> (1, 2, 3) + (4, 5, 6, 7)
(1, 2, 3, 4, 5, 6, 7)

>>> (1, 2, 3) * 4
(1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3)

>>> (1, 2, 3, 4, 5, 6, 7)[2 : 4+1]
(3, 4, 5)
>>> (1, 2, 3, 4, 5, 6, 7)[ : : -1]
(7, 6, 5, 4, 3, 2, 1)

Voici le très important nulluplet, qui sera le point de départ pour construire des uplets plus grands. C'est un élément neutre à gauche et à droite pour la concaténation. >>> u = ()
>>> type(u)
<class 'tuple'>
>>> len(u)
0

Reste à voir la petite subtilité des singulets : si on place un objet entre des parenthèses pour faire un uplet de longueur un, on est très déçu… >>> u = (42)
>>> type(u)
<class 'int'>

…parce qu'évidemment dans ce cas les parenthèses sont interprétées comme des parenthèses de priorité. Pour faire ce qu'on veut, il faut ajouter une virgule. >>> u = (42,)
>>> type(u)
<class 'tuple'>
>>> len(u)
1

?

def SousUplet(u, a, b, pas = 1) :
    su = () ; k = a
    while (k - b) * pas < 0 :
        su += (u[k],) ; k += pas
    return su

?


2 - Multi-affectations, opérateur de dépaquetage, fonctions multi-aires


a) Affectations multiples

?

def ?

b) Opérateur de dépaquetage

?

def ?

c) Retour sur les arguments facultatifs, fonctions multi-aires

?

def ?
?

def ?
?

def ?
?


3 - Quelques problèmes d'énumération

a) Tous les uplets

?

def Couples(L) :
    C = []
    for x in L :
        for y in L :
            C.append( (x, y) )
    return C

?

def Couples(A, B) :
    C = []
    for a in A :
        for b in B :
            C.append( (a, b) )
    return C

Faisons encore mieux et écrivons un programme qui englobe les deux précédents. Pour cela, on rend le deuxième argument facultatif ; on n'a pas le droit de lui donner comme valeur par défaut le premier argument (car les valeurs par défaut doivent être explicites) mais on peut ruser un peu pour contourner cette difficulté.

def Couples(A, B = None) :
    if B == None :
        B = A
    C = []
    for a in A :
        for b in B :
            C.append( (a, b) )
    return C

Passons aux uplets quelconques.

def Uplets(L, k) :
    U = [ () ]
    for i in range(k) :
        Nouveaux = []
        for u in U :
            for x in L :
                Nouveaux.append( u + (x,) )
        U = Nouveaux
    return U

?

def Uplets(*Listes) :
    U = [ () ]
    for i in range(len(Listes)) :
        Nouveaux = []
        for u in U :
            for x in Listes[i] :
                Nouveaux.append( u + (x,) )
        U = Nouveaux
    return U

?

b) Parties

?

def Parties(L) :
    P = [ [] ]
    for x in L :
        Nouvelles = []
        for p in P :
            Nouvelles.extend( [p, p + [x]] )
        P = Nouvelles
    return P

?

def Partie(L, χ) :
    p = []
    for i in range(len(χ)) :
        if χ[i] == 1 :
            p.append( L[i] )
    return p

?

def IncrémenterOdomètre(χ) :
    χ[0] += 1
    i = 0
    while i < len(χ) - 1 and χ[i] == 2 :
        χ[i] = 0 ; i += 1 ; χ[i] += 1
    # Cas où l'on fait « le tour » du compteur
    if χ[-1] == 2 :
        χ[-1] = 0

?

def Parties(L) :
    P = [] ; χ = [0] * len(L)
    for i in range(2 ** len(L)) :
        P.append( Partie(L, χ) )
        IncrémenterOdomètre(χ)
    return P

c) Parties à \(k\) éléments

?

def IncrémenterÀUnsConstants(χ) :
    # Premier un suivi d'un zéro
    i = 0 ; nb_uns = 0
    while i < len(χ) - 1 and (χ[i] == 0 or χ[i+1] == 1) :
        nb_uns += χ[i] ; i += 1
    # On vérifie si l'on a fini l'énumération
    if i == len(χ) - 1 :
        return False
    else :
        χ[i] = 0 ; χ[i+1] = 1
        for k in range(nb_uns) :
            χ[k] = 1
        for k in range(nb_uns, i) :
            χ[k] = 0
        return True

def Parties_à_k_éléments(L, k) :
    P = [] ; χ = [1] * k + [0] * (len(L) - k) ; Continuer = True
    while Continuer :
        P.append( Partie(L, χ) )
        Continuer = IncrémenterÀUnsConstants(χ)
    return P

?

d) Anagrammes

?

def UnDePlus(Objets, x) :
    i = 0
    while i < len(Objets) and Objets[i][0] != x :
        i += 1
    if i == len(Objets) :
        Objets.append( (x, 1) )
    else :
        Objets[i] = (x, Objets[i][1] + 1)

?

def Compter(L) :
    Objets = []
    for x in L :
        UnDePlus(Objets, x)
    return Objets

?

def CasesVides(Partielle) :
    C = []
    for i in range(len(Partielle)) :
        if Partielle[i] == None :
            C.append(i)
    return C

?

def PositionnerObjet(Cases, Positions, Objet) :
    p = list(Cases)
    for i in Positions :
        p[i] = Objet
    return p

?

def AjouterObjet(Partielles, Objet, k) :
    Nouvelles = []
    for p in Partielles :
        for Positions in Parties_à_k_éléments(CasesVides(p), k) :
            Nouvelles.append(PositionnerObjet(p, Positions, Objet))
    return Nouvelles

?

def Anagrammes(L) :
    Objets = Compter(L)
    Partielles = [[None] * len(L)]
    for (Objet, Effectif) in Objets :
        Partielles = AjouterObjet(Partielles, Objet, Effectif)
    return Partielles

e) Permutations

On va voir une méthode un peu plus simple, et surtout plus efficace (parce qu'elle permet de les énumérer sans les construire toutes) pour générer les anagrammes d'une liste dont tous les éléments sont distincts (donc ses permutations).
    On commence par supposer que les objets de la liste sont des entiers, ce qui permet en particulier de les ordonner, et d'énumérer les permutations dans l'ordre lexicographique (c'est comme l'ordre alphabétique, sauf que les lettres sont remplacées par des nombres et les mots par des listes de nombres).

def ÉchangerAvecLePlusPetit(Q, x) :
    i = 0
    while Q[i] < x :
        i += 1
    y = Q[i] ; Q[i] = x
    return y

def PermutationSuivante(L) :
    i = len(L) - 1
    while i > 0 and L[i-1] > L[i] :
        i -= 1
    if i == 0 :
        return None
    else :
        Q = L[len(L)-1 : i-1 : -1]
        x = ÉchangerAvecLePlusPetit(Q, L[i-1])
        return L[ : i-1] + [x] + Q

def PermutationsEntiers(L) :
    P = []
    p = list(L)
    while p != None :
        P.append(p)
        p = PermutationSuivante(p)
    return P

Reste à voir comment faire pour une liste quelconque d'objets, y compris s'il n'y a pas de relation d'ordre entre eux (par exemple s'ils ne sont pas tous du même type). def Permutations(L) :
    P = [] ; ind = [i for i in range(len(L))]
    while ind != None :
        P.append( [L[i] for i in ind] )
        ind = PermutationSuivante(ind)
    return P