CIRM Tutoriel 3 (français) system:sage

Structure de données en Sage (et Python)

Listes, n-uplets, dictionnaires et chaînes de caractères

Écrit par Franco Saliola le 23 février 2010

Traduit en français par Sébastien Labbé le 4 mars 2010

Listes

Création de listes I: [crochets]

Exemple:

{{{id=34| L = [3, Permutation([5,1,4,2,3]), 17, 17, 3, 51] /// }}} {{{id=124| L /// [3, [5, 1, 4, 2, 3], 17, 17, 3, 51] }}} {{{id=273| /// }}}

Exercice: Créer la liste [63, 12, -10, 'a', 12]. Assigner-la à la variable L. Afficher-la (à l'aide de la commande print).

{{{id=123| /// }}} {{{id=113| /// }}}

Exercice: Créer la liste vide. (Vous aurez souvent besoin de faire cela.)

{{{id=112| /// }}} {{{id=79| /// }}}

Creation de listes II: range

La fonction range permet de construire facilement une liste d'entiers. Voici la documentation de la fonction range. 

Documentation:

range([start,] stop[, step]) -> liste d'entiers

Retourne une liste contenant une suite arithmétique d'entiers.
range(i, j) retourne [i, i+1, i+2, ..., j-1]; la valeur par défaut 
de start est 0. La variable step, lorsque spécifiée, permet de définir
le pas (négatif ou positif). Par exemple, range(4) retourne [0, 1, 2, 3].
La dernière valeure est omise! Ces nombres sont les indices valides
d'une liste de 4 éléments.

Exercice: Utiliser range pour construire la liste $[1,2,\ldots,50]$.

{{{id=306| /// }}} {{{id=305| /// }}} {{{id=304| /// }}} {{{id=307| /// }}} {{{id=281| i = 3 /// }}} {{{id=46| type(i) /// }}} {{{id=282| j = range(3)[1] /// }}} {{{id=283| type(j) /// }}} {{{id=284| for i in range(1,10): j = Integer(i) print j.factor() /// 1 2 3 2^2 5 2 * 3 7 2^3 3^2 }}} {{{id=285| /// }}} {{{id=40| /// }}}

Exercice: Utiliser range pour construire la liste des nombres pairs entre 1 et 100 (le nombre 100 inclu).

{{{id=44| /// }}} {{{id=43| /// }}}

Exercice: L'argument step pour la fonction range peut-être négatif. Utiliser range pour construire la liste $[10, 7, 4, 1, -2]$.

{{{id=47| /// }}} {{{id=48| /// }}}

Creation de listes III: compréhension de listes

Les compréhensions de listes permettent de créer une liste à partir d'une autre de manière très concise.

Exemple. Nous savons déjà comment créer la liste $[1, 2, \ldots, 16]$:

range(1,17)

En utilisant une compréhension de liste, on peut créer la liste $[1^2, 2^2, 3^2, ..., 16^2]$ comme suit :

[i^2 for i in range(1,17)]
{{{id=121| [i^2 for i in range(1,17)] /// [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256] }}} {{{id=137| sum([i^2 for i in range(1,17)]) /// 1496 }}} {{{id=136| /// }}}

Projet Euler Problème 6

La somme des carrés des dix premiers nombres entiers strictement positif est

1^(2) + 2^(2) + ... + 10^(2) = 385.

Le carré de la somme des dix premiers nombres entiers strictement positifs est

(1 + 2 + ... + 10)^(2) = 55^(2) = 3025.

Donc, la différence entre le carré de la somme des dix premiers nombres entiers strictement positifs et la somme de leurs carrés est 3025 − 385 = 2640.

Trouver la différence entre le carré de la somme des cents premiers nombres entiers strictement positifs et la somme de leurs carrés.

{{{id=119| /// }}} {{{id=118| /// }}} {{{id=130| /// }}} {{{id=129| /// }}}

Filtrer une liste avec une compréhension de liste

Une liste peut être filtrée en utilisant une compréhension de liste.

Exemple: Pour créer la liste des carrés des nombres premiers entre 1 et 100, on utilise la compréhension de liste suivante.

{{{id=128| [p^2 for p in [1,2,..,100] if is_prime(p)] /// [4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409] }}} {{{id=135| /// }}} {{{id=134| /// }}}

Exercice: Utiliser une compréhension de liste pour lister tous les nombres naturels plus petits que 20 qui sont multiples de 3 ou 5.

Indices:

  1. Pour obtenir le reste de la division de 7 par 3, utiliser 7%3.
  2. Pour tester l'égalité, utiliser les deux signes d'égalité (==) ; par exemple, 3 == 7.
{{{id=132| /// }}} {{{id=139| /// }}} {{{id=138| /// }}}

Compréhensions de listes emboîtées

Les compréhensions de listes peuvent s'emboîter!

Exemples:

{{{id=115| [(x,y) for x in range(5) for y in range(3)] /// [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2)] }}} {{{id=144| matrix([[x^i for i in range(8)] for x in range(1,6)]) /// [ 1 1 1 1 1 1 1 1] [ 1 2 4 8 16 32 64 128] [ 1 3 9 27 81 243 729 2187] [ 1 4 16 64 256 1024 4096 16384] [ 1 5 25 125 625 3125 15625 78125] }}} {{{id=114| /// }}}

Exercice: 

Un  triplet pythagoricien est un triplet $(x,y,z)$ d'entiers strictement positifs qui satisfont $x^2+y^2=z^2$. 

Les triplets Pythagoriciens dont les valeurs ne dépassent pas $10$ sont :  $[(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]$.

En utilisant une compréhension de liste filtrée, construire la liste des triplets Pythagoriciens dont les valeurs n'excèdent pas $50$.

{{{id=78| /// }}} {{{id=69| /// }}}

Accéder aux éléments d'une liste

Pour accéder aux éléments d'un liste, utiliser la syntaxe L[i], où i désigne l'indice de l'élément.

Exercice: 

  1. Construire la liste L = [1,2,3,4,5,6]. Quelle est la valeur de L[3]?
  2. Quelle est la valeur de L[1]?
  3. Quel est l'indice du premier élément de L?
  4. Quelle est la valeur de L[-1]? de L[-2]?

 

{{{id=39| /// }}} {{{id=2| /// }}}

Modifier une liste: modifier un élément d'une liste

Pour changer l'élément en position i d'une liste L:

{{{id=160| L = ["a", 4, 1, 8] /// }}} {{{id=170| L[2] = 0 /// }}} {{{id=159| L /// }}} {{{id=172| /// }}} {{{id=171| /// }}}

Modifier une liste: append et extend

Pour ajouter un élément à une liste, utilser la méthode append :

{{{id=157| L = ["a", 4, 1, 8] /// }}} {{{id=173| L.append(17) /// }}} {{{id=174| L /// ['a', 4, 1, 8, 17] }}} {{{id=156| /// }}}

Pour étendre une liste par une autre liste, utilser la méthode extend :

{{{id=177| L1 = [1,2,3] L2 = [7,8,9,0] /// }}} {{{id=179| L1.extend(L2) /// }}} {{{id=180| L1 /// [1, 2, 3, 7, 8, 9, 0] }}} {{{id=175| /// }}}

Modifier une liste : reverse, sort, ...

{{{id=153| L = [4,2,5,1,3] /// }}} {{{id=152| L.reverse() /// }}} {{{id=151| L /// [3, 1, 5, 2, 4] }}} {{{id=150| L.sort() /// }}} {{{id=149| L /// [1, 2, 3, 4, 5] }}} {{{id=148| /// }}} {{{id=280| L = [3,1,6,4] /// }}} {{{id=279| sorted(L) /// [1, 3, 4, 6] }}} {{{id=253| L /// [3, 1, 6, 4] }}}

Concaténation de listes

Pour concaténer deux listes, utiliser l'addition (+). Cette opération n'est pas commutative.....

{{{id=252| L1 = [1,2,3] L2 = [7,8,9,0] /// }}} {{{id=251| L1 + L2 /// [1, 2, 3, 7, 8, 9, 0] }}} {{{id=147| L1 /// [1, 2, 3] }}} {{{id=255| L2 /// [7, 8, 9, 0] }}} {{{id=260| /// }}} {{{id=259| /// }}}

Trancher une liste

Vous pouvez trancher une liste en utilisant la syntaxe L[start : stop : step]. Ceci retourne une sous-liste de L.

Exercice: Voici quelques exemples de listes tranchées. Deviner le résultat de chaque cellule avant de l'évaluer.

{{{id=262| L = range(20) L /// }}} {{{id=261| L[3:15] /// }}} {{{id=258| L[3:15:2] /// }}} {{{id=266| L[15:3:-1] /// }}} {{{id=264| L[:4] /// }}} {{{id=271| L[:] /// }}} {{{id=270| L[::-1] /// }}} {{{id=269| /// }}} {{{id=268| /// }}}

AVERTISSEMENT!

{{{id=288| u = [3,4] /// }}} {{{id=290| u /// [3, 4] }}} {{{id=291| L = [u, u, u] /// }}} {{{id=287| L /// [[3, 4], [3, 4], [3, 4]] }}} {{{id=267| flatten(L) /// [3, 4, 3, 4, 3, 4] }}} {{{id=292| u.append(17) /// }}} {{{id=257| u /// [3, 4, 17] }}} {{{id=256| L /// [[3, 4, 17], [3, 4, 17], [3, 4, 17]] }}} {{{id=294| L = [u[:], u[:], u[:]] /// }}} {{{id=293| L /// [[3, 4, 17], [3, 4, 17], [3, 4, 17]] }}} {{{id=297| u.append(18) /// }}} {{{id=296| L /// [[3, 4, 17], [3, 4, 17], [3, 4, 17]] }}} {{{id=300| /// }}} {{{id=299| /// }}} {{{id=298| /// }}} {{{id=295| /// }}}

Exercice: Revoyons la fonction de Syracuse. À partir de $6$ et en appliquant continuellement la fonction de Syracuse, on obtient la suite $$6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, \ldots$$ Écrire une fonction qui prend un entier positif et qui retourne une liste des termes de la suite jusqu'à ce que le nombre 1 soit atteint. Par exemple, en commençant avec 6, la fonction doit retourner $$[6,3,10,5,16,8,4,2,1].$$

{{{id=146| def syracuse(n): if n % 2 == 0: return n/2 else: return 3*n+1 /// }}} {{{id=248| /// }}} {{{id=247| /// }}} {{{id=246| /// }}}

Exercice: La fonction suivante contient une boucle et quelques opérations sur les listes définies précédemment. Qu'est-ce que la fonction retourne?

{{{id=276| def f(nLoops): L = [1] for n in range(2, nLoops): L = [sum(L[:i]) for i in range(n-1, -1, -1)] return numerical_approx(2*L[0]*len(L)/sum(L), digits=50) /// }}} {{{id=308| for i in range(1,10): print f(i) /// }}} {{{id=275| /// }}} {{{id=274| /// }}} {{{id=21| /// }}}

n-uplets (Tuples)

Un tuple est une liste immuable, ce qui signifie qu'on ne peut pas le changer une fois créé.

Les parenthèses sont utilisées pour créer un tuple.

{{{id=244| t = (3, 5, [3,1], (17,[2,3],17), 4) t /// (3, 5, [3, 1], (17, [2, 3], 17), 4) }}} {{{id=301| t.index(5) /// 1 }}} {{{id=243| len(t) /// 5 }}}

Les tuples se comportent comme les listes:

Opérations Syntaxe pour les listes Syntaxe pour les tuples
Accéder à une lettre
 list[3] tuple[3]
Concaténation list1 + list2 tuple1 + tuple2
Tranches list[3:17:2] tuple[3:17:2]
Une copie inversée.
 list[::-1] tuple[::-1]
Longueur len(list) len(tuple)
{{{id=241| /// }}} {{{id=240| /// }}} {{{id=239| /// }}} {{{id=238| /// }}} {{{id=237| /// }}} {{{id=236| /// }}} {{{id=235| /// }}} {{{id=234| /// }}} {{{id=233| /// }}} {{{id=232| /// }}} {{{id=231| /// }}} {{{id=230| /// }}}

Dictionnaires

Un dictionnaire est une autre structure de donnée de Python. Contrairement aux listes qui sont indicées par des nombres, les dictionnaires sont indicés par des clées qui peuvent être n'importe quel objet immuable. Les chaînes de caractères peuvent être utilisées comme clés, car ils sont immables.

Il y a plusieurs façons de définir des dictionnaires. Voici trois manières équivalentes de définir un dictionnaire qui associe 'cle' avec 'valeur' et 'key' avec 'value'.

{{{id=310| {'cle':'valeur', 'key':'value'} /// {'cle': 'valeur', 'key': 'value'} }}} {{{id=309| dict(cle='valeur', key='value') /// {'cle': 'valeur', 'key': 'value'} }}} {{{id=311| d = {} d['cle'] = 'valeur' d['key'] = 'value' d /// {'cle': 'valeur', 'key': 'value'} }}} {{{id=312| /// }}} {{{id=183| d = {3:17, "key":[4,1,5,2,3], (3,1,2):"goo"} d /// {3: 17, (3, 1, 2): 'goo', 'key': [4, 1, 5, 2, 3]} }}} {{{id=303| /// }}} {{{id=302| /// }}} {{{id=186| /// }}}

Les dictionnaires se comportes comme les listes et les tuples pour plusieurs opérations importantes.

Opération Syntaxe pour les listes Syntaxe pour les dictionnaires
Accéder aux éléments
 L[3] D["key"]
Taille len(L) len(D)
Modifier L[3] = 17 D["key"] = 17
Supprimer des éléments del L[3] del D["key"]
{{{id=190| /// }}} {{{id=195| /// }}}

Exercice: Considérer le graphe orienté suivant. 

Créer un dictionnaire dont les clés sont les sommets du graphe ci-haut et où chaque clé est associée à une liste des sommets adjacents. Par exemple, le sommet 1 pointe vers les sommets de la liste [2, 3], alors le dictionnaire commencera avec {1:[2,3], 

{{{id=192| d = { 0: [2,1,1], 1:[2,3] , /// }}} {{{id=222| /// }}} {{{id=221| /// }}}

Exercice: Utiliser la commande DiGraph pour construire le graphe orienté ci-haut et dessiner-le. (Indice: Dans la documentation pour DiGraph, rechercher les exemples de la section 'dictionary of lists'.)

{{{id=220| /// }}} {{{id=219| /// }}} {{{id=217| /// }}} {{{id=216| /// }}}

Les sept ponts de Königsberg

Exercice: Les Sept ponts de Königsberg est un problème historique résolu par Leonhard Euler en 1735. C'est un problème issu de la théorie des graphes.

"La ville de Königsberg (aujourd'hui Kaliningrad) est construite autour de deux îles reliées entre elles par un pont et six ponts relient le continent à l'une ou l'autre des deux îles. Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts."

  1. Construire le graphe de droite en Sage. Utiliser la commande Graph plutôt que DiGraph.
  2. Résoudre le problème, c'est-à-dire est-ce qu'un tel chemin existe? (Indice: Regarder la documentation de la méthode eulerian_circuit ; regarder la définition de circuit Eulerien dans Wikipédia si vous ne connaissez pas la définition.)

(La citation et les images proviennent de la page Wikipédia Seven Bridges of Königsberg;
le problème est de William Stein's Graph Theory Worksheet for Math 480b [2009])

{{{id=215| /// }}}

Chaînes de caractères

Sage inclut une structure de donnée pour les chaînes de caractères.

Il y a plusieurs façons de créer des chaînes de caractères. On peut utiliser les simples guillemets (') où les doubles guillemets (") :

{{{id=214| s = "This is a string!" s /// }}} {{{id=213| print s /// }}} {{{id=224| s2 = "This is a multi-line\n string" s2 /// }}} {{{id=272| print s2 /// }}} {{{id=223| /// }}}

 

Les chaînes de caractères se comportent de la même façon que les listes et les tuples. Par exemple,

Opération Syntaxe pour les listes Syntaxe pour les tuples Syntaxe pour les chaînes de caractères
Accéder à un élément
list[3] tuple[3] string[3]
 Concaténation list1 + list2 tuple1 + tuple2 string1 + sting2
 Tranches list[3:17:2] tuple[3:17:2]  string[3:17:2]
 Une copiée inversée
 list[::-1] tuple[::-1]  string[::-1]
Longueur len(list) len(tuple) len(string)
{{{id=212| /// }}} {{{id=210| /// }}}

Construire une chaîne de caractères

Une manière de construire une chaîne de caractères est d'utiliser %s qui se remplace par de l'information fournie:

{{{id=208| print "%s * %s = %s" % (4, 3, 4*3) print "%s * %s = %s" % (4368, 312389, 4368 * 312389) /// }}} {{{id=207| /// }}}

Si vous voulez fixer la longueur de la chaîne à insérer, utiliser %15s , ce qui allouera 15 caractères. C'est pratique pour alligner des blocs de texte.

{{{id=229| /// }}} {{{id=228| /// }}} {{{id=206| /// }}}

Exercice: Écrire une boucle ou une fonction qui affiche les $n$ premières rangées du triangle de Pascal. Pour $n=9$, le résultat devrait ressembler à ceci :

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
{{{id=205| /// }}}

Exercice: La transformée de Burrows-Wheeler Transform (BWT) d'une chaîne de caractères s trie toutes les rotations de s et retourne la dernière colonne.

Par exemple, si on trie les rotations de 'bananas', alors on obtient la liste :

    ananasb
    anasban
    asbanan
    bananas
    nanasba
    nasbana
    sbanana

Les lettres dans la dernière colonne sont (dans l'ordre) b, n, n, s, a, a, a. Alors la BWT de bananas est bnnsaaa.

Écrire une fonction qui retourne la BWT d'une chaîne de caractères. Calculer la BWT de bananas, ananas et cocomero. (Indice: Vour pouvez retourner le résultat sous forme de liste, mais si vous voulez retourner le résultat sous forme de chaîne de caractères, vous pouvez considérer l'utilisation de la méthode join définie pour les chaîne de caractères.)

{{{id=204| /// }}} {{{id=203| /// }}} {{{id=202| /// }}} {{{id=201| /// }}} {{{id=200| /// }}} {{{id=199| /// }}} {{{id=198| /// }}} {{{id=197| /// }}} {{{id=196| /// }}} {{{id=193| /// }}} {{{id=194| /// }}}