Quelques problèmes classiques d’énumération

Contenu

Quelques problèmes classiques d’énumération#

Sous-ensembles#

Comptage#

Je tiens dans ma main 4 cartes différentes (qu’on appellera « Rouge », « Bleue », « Verte », et « Jaune »). Je peux déposer dans la pioche un sous-ensemble de mes cartes (entre 0 et 4). Combien ai-je de possibilités ?

.

Comment le calculer en Sage ?

Hand = Set(["Rouge","Bleue","Verte","Jaune"])
Hand

Hand.subsets()

Hand.subsets().cardinality()

hand_subsets = Hand.subsets()
hand_subsets.cardinality??

list(hand_subsets)

hand_subsets.random_element()

Une première méthode de tirage aléatoire (complexité \(O(|s|)\)):

def random_subset(s):
    """
    Renvoie un sous ensemble aléatoire de `s` uniformément
    Input :
     - s un ensemble 
    Output : un sous ensemble de s
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 71");

random_subset(Hand)

def distribution(L):
    """
    Renvoie la distribution par nombre d'occurences d'une liste d'éléments
    Input :
     - une liste L d'éléments (non mutables)
    Output: un dictionnaire comptant les occurences de chaque élément de la liste L
    """
    d = {}
    for el in L:
        d[el] = d.get(el, 0) + 1
    return d

distribution([random_subset(Hand) for i in range(10000)])

Listage par bijection et unrank#

On va définit une bijection (une correspondance 1 à 1) entre les nombres de \(0\) à \(2^n - 1\) et les sous-ensembles d’un ensemble de \(n\) éléments.

Un nombre entre 0 et \(2^n - 1\) est représenté en binaire par une liste de \(n\) bits, chaque bit prend comme valeur \(0\) ou \(1\).

Exemple : \(13 = 2^0 + 2^2 + 2^3 = (1101)_2\)

Chaque bit correspond à un élément de l’ensemble, si le bit est à 1, l’élément est présent.

Dans l’exemple ci-dessous, les bits correspondent respectivement à « Rouge », « Bleu », « Vert », « Jaune » (du poids fort au poids faible). Dans la suite, l’ordre n’aura pas d’importance, on utilisera l’ordre donné par l’ensemble Hand qui n’est pas forcément celui là.

\( \begin{align} 0 &= 0000 & \leftrightarrow & \emptyset \\ 1 &= 0001 & \leftrightarrow & \{J\} \\ 2 &= 0010 & \leftrightarrow & \{V \} \\ 3 &= 0011 & \leftrightarrow & \{V,J \} \\ 4 &= 0100 & \leftrightarrow & \{B \} \\ 5 &= 0101 & \leftrightarrow & \{B, J \} \\ 6 &= 0110 & \leftrightarrow & \{B,V \} \\ 7 &= 0111 & \leftrightarrow & \{B,V,J \} \\ 8 &= 1000 & \leftrightarrow & \{R \} \\ 9 &= 1001 & \leftrightarrow & \{R,J\} \\ 10 &= 1010 & \leftrightarrow & \{R,V \} \\ 11 &= 1011 & \leftrightarrow & \{R,V,J \} \\ 12 &= 1100 & \leftrightarrow & \{R,B \} \\ 13 &= 1101 & \leftrightarrow & \{R,B, J \} \\ 14 &= 1110 & \leftrightarrow & \{R,B,V \} \\ 15 &= 1111 & \leftrightarrow & \{R,B,V,J \} \\ \end{align} \)

def unrank_subset(i, s):
    """
    Renvoie le sous ensemble de s correspondant à i 
    Input:
     - i un entier entre 0 et 2^|s| - 1
     - s un ensemble de type Set
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 147");

unrank_subset(0,Hand)

unrank_subset(15,Hand)

unrank_subset(1,Hand)

unrank_subset(2,Hand)

unrank_subset(4,Hand)

unrank_subset(8,Hand)

def subsets_by_unrank(s):
    """
    Renvoie un itérateur sur l'ensemble des sous-ensembles de s en utilisant unrank
    Input :
     - un ensemble s
    Output : un itérateur sur les sous-ensembles de s
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 184");

list(subsets_by_unrank(Hand))

def random_subset_by_unrank(s):
    """
    Renvoie un sous-ensemble alétoire uniformément en utilisant unrank
    Input :
     - s un ensemble 
    Output : un sous ensemble de s
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 201");

random_subset_by_unrank(Hand)

distribution([random_subset(Hand) for i in range(10000)])

Listage récursif#

On peut aussi concevoir l’algorithme de la façon suivante :

si l’ensemble \(S\) est vide alors le seul sous-ensemble existant est l’ensemble vide
sinon, on choisit un élément \(t \in S\). Les sous-ensembles de \(S\) sont
- les sous-ensembles de \(S \setminus t\)
- les sous-ensembles de \(S \setminus t\) auxquels on ajoute \(t\)

Note : quelques méthodes utiles sur les Set de Sage

len(Hand)

Hand.an_element()

Hand + Set(["Noire"])

Hand - Set(["Bleue"])

def subsets_recurs(s):
    """
    Renvoie un itérateur sur l'ensemble des sous-ensembles de s par algo récursif
    Input :
     - un ensemble s de type Set
    Output : un itérateur sur les sous-ensembles de s
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 248");

list(subsets_recurs(Hand))

Arrangements, permutations, combinaisons#

Un arrangement de \(k\) éléments parmi un ensemble \(S\) est un choix ordonné de \(k\) éléments parmi \(S\). Par exemple : \(Rouge,Verte\) est un arrangement de 2 éléments parmi les 4 cartes que j’ai en main, et \(Verte, Rouge\) en est un autre.

Arrangements(Hand, 2)

Combien ai-je d’arrangements de 2 parmi 4 ?

Arrangements(Hand, 2).cardinality()

pourquoi ? J’ai 4 choix pour la première carte fois 3 choix pour la seconde carte.

list(Arrangements(Hand,2))

De façon générale, il y a

\[n \times (n-1) \times \dots \times (n- k +1) = \frac{n!}{(n-k)!}\]

arrangements de \(k\) parmi \(n\).

Arrangements(Hand,1).cardinality() # 4! / 3!

Arrangements(Hand,2).cardinality() # 4! / 2!

Arrangements(Hand,3).cardinality() # 4! / 1!

Les arrangements de \(n\) éléments parmi un ensemble \(S\) de taille \(n\) sont les permutations de \(S\), comptées par \(n!\)

Arrangements(Hand,4).cardinality()

list(Arrangements(Hand,4))

Une combinaison de \(k\) élements parmi un ensemble \(S\) de taille \(n\) est un choix de \(k\) élements de \(S\) mais cette fois, l’ordre des éléments ne compte pas. Par exemple \(\{ Rouge, Verte \} = \{ Verte, Rouge \}\) est une combinaison de 2 cartes parmi les 4 que j’ai en main.

Combinations(Hand,2)

Observez la liste des arrangements de 2 cartes parmi les 4, lesquels correspondent à la même combinaison ? Combien a-t-on de combinaisons différentes au total ?

Combinations(Hand,2).cardinality()

list(Combinations(Hand,2))

Soit \(\{ a,b,c \} \) une combinaison de 3 éléments. Il existe \(6 = 3!\) arrangements correspondant : ce sont les 6 façons d’ordonner les éléments \(a\), \(b\), et \(c\). De façon générale, une combinaison de \(k\) éléments correspond à \(k!\) arrangements. On obtient alors la formule suivante :

\[ C_n^k = \frac{A_n^k}{k!} = \frac{n!}{(n-k)!\,k!} \]

où \(C_n^k\) (qu’on écrit aussi \(n \choose k\)) est le nombre de combinaisons de \(k\) parmi \(n\) et \(A_n^k\), le nombre d’arrangements.

Combinations(Hand,0).cardinality()

Combinations(Hand,1).cardinality()

Combinations(Hand,2).cardinality()

Combinations(Hand,3).cardinality()

Combinations(Hand,4).cardinality()

Remarquez que la somme de toutes les combinaisons possibles donne : \(1+4+6+4+1 = 16 = 2^4\). En effet, les combinaisons de \(k\) parmi \(n\) pour \(k\) allant de 0 à \(n\), sont les sous-ensembles !

Exercice TP (cf rapport) Implantez (avec l’algorithme de votre choix) des fonctions permettant de lister les arrangements / combinaisons et d’en tirer au hasard de façon uniforme.

Produits cartésiens#

Le produit cartésien \(A \times B\) de deux ensembles \(A\) et \(B\) est l’ensemble des couples \((a,b)\) où \(a\in A\) et \(b\in B\).

Couleurs = Set(["Pique", "Coeur", "Carreau", "Trèfle"])
Numero = Set(["As","2","3","4","5","6","7","8","9","10","V","D","R"])
Cartes = cartesian_product([Couleurs, Numero])
Cartes

Cartes.cardinality()

Couleurs.cardinality() * Numero.cardinality()

Cartes.an_element()

list(Cartes)

Listage récursif#

def produits_recurs(s1, s2):
    """
    Renvoie un itérateur sur les élements du produit cartésien entre s1 et s2
    Input :
       - s1, un ensemble de type Set
       - s2, un ensemble de type Set
    Output : un itérateur sur tous les tuples (e1,e2) avec e1 dans s1 et e2 dans s2
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 393");

list(produits_recurs(Couleurs, Numero))

len(list(produits_recurs(Couleurs, Numero)))

def random_produit(s1,s2):
    """
    Renvoie un élément tiré uniformément dans le produit de s1 x s2
    Input :
       - s1, un ensemble de type Set
       - s2, un ensemble de type Set
    Output : un element (e1,e2) avec e1 dans s1 et e2 dans s2 tiré uniformément
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 415");

random_produit(Couleurs, Numero)

Unrank#

Voyons aussi comment écrire une méthode « unrank ». L’idée est de définir un « ordre » sur les élements et de les numéroter. On va supposer qu’il existe un ordre des éléments dans s1 et s2 (en les transformant en liste et en prenant l’ordre obtenu)

list(Couleurs)

list(Numero)

Les éléments du produit sont ordonnés d’abord par le premier élément (issu de s1) puis par le second élément (issu de s2). Leur rang est leur numéro dans la liste des éléments. La méthode unrank permet d’obtenir l’élément correspondant à un numéro donné sans parcourir la liste !

def unrank_produit(i,s1,s2):
    """
    Renvoie l'élément correspondant au numéro i dans la liste des éléments du produit cartésien
    Input :
       - i, un entier entre 0 et len(s1) * len(s2) - 1
       - s1, un ensemble de type Set
       - s2, un ensemble de type Set
    Output: l'élément (e1,e2) correspondant à i
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 448");

unrank_produit(0,Couleurs,Numero)

unrank_produit(51,Couleurs,Numero)

[unrank_produit(i,Couleurs,Numero) for i in range(Couleurs.cardinality() * Numero.cardinality())] == \
list(produits_recurs(Couleurs, Numero))

Application : les arbres binaires#

Un arbre binaire est défini de la façon récursive suivante, c’est :

soit un arbre vide (une feuille)
soit un noeud avec un sous-arbre à gauche et un sous-arbre à droite qui sont tous les deux des arbres binaires

La taille d’un arbre binaire est son nombre de noeuds (on ne compte pas les feuilles).

Les arbres binaires sont implanté en Sage :

BinaryTree() # une feuille

BinaryTree([BinaryTree(), BinaryTree()]) # un arbre avec une feuille à gauche et une feuille à droite

ascii_art(BinaryTree([BinaryTree(), BinaryTree()]))

leaf = BinaryTree()
bt1 = BinaryTree([BinaryTree([leaf, leaf]), leaf]) # un arbre binaire de taille 2
ascii_art(bt1) 

leaf = BinaryTree()
bt2 = BinaryTree([leaf, BinaryTree([leaf, leaf])]) # un arbre binaire de taille 2
ascii_art(bt2)

Exercice :

Faites à la main la liste des arbres binaires de taille 3
Combien a-t-on d’arbres binaires de taille 4 ? 5 ? 6 ?
Trouvez une expression récursive pour la suite \(C_n\) du nombre d’arbre binaire de taille n

Les nombres \(C_n\) sont en réalité bien connus, on les appelle les nombres de Catalan. On verra la semaine prochaine comment on prouve que les arbres binaires sont comptés par les nombres de Catalan.

BT3 = BinaryTrees(3)
ascii_art(list(BT3))

BT3.cardinality()

BT3.cardinality??

Pour aujourd’hui, on va se contenter de la formule récursive et implanter les méthodes suivantes :

@cached_function
def cardinality_binaryTrees(n):
    """
    Renvoie le nombre d'arbres binaires de taille n
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 529");

cardinality_binaryTrees(3)

cardinality_binaryTrees(4)

cardinality_binaryTrees(5)

assert all(cardinality_binaryTrees(n) == catalan_number(n) for n in range(20))

cardinality_binaryTrees(100)

catalan_number(100)

def binarytrees(n):
    """
    Renvoie un itérateur sur les arbres binaires de taille n
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 563");

list(binarytrees(3))

ascii_art(list(binarytrees(3)))

def unrank_binarytree(i,n):
    """
    Renvoie l'arbre binaire correspondant au numero i dans la liste des arbres binaires
    (selon l'ordre de la fonction binarytrees)
    """
    
    // Remplacer la ligne suivante par le code adéquat
    raise RuntimeError("code non implanté ligne 582");

ascii_art(unrank_binarytree(0,3))

ascii_art(unrank_binarytree(1,3))

ascii_art(unrank_binarytree(2,3))

ascii_art(unrank_binarytree(3,3))

ascii_art(unrank_binarytree(4,3))

def random_binarytree(n):
    """
    Renvoie un arbre binaire de taille n tiré uniformément
    """
    card = cardinality_binaryTrees(n)
    i = randint(0,card-1)
    return unrank_binarytree(i,n)

ascii_art(random_binarytree(5))

ascii_art(random_binarytree(50))

bt = random_binarytree(100)
bt

bt.node_number()