Conjunts

Aquesta lliçó introdueix un nou tipus de dades: els conjunts. Els conjunts de Python són molt semblants als que s’usen en matemàtiques i per això el seu ús és molt senzill i intuïtiu. Gràcies a l’ús de conjunts, els programes poden ser més expressius i eficients que les seves alternatives amb llistes.

Introducció

Un conjunt és un tipus de dades que permet emmagatzemar una col·lecció d’elements sense repeticions amb les operacions principals següents:

A més, els elements del conjunt es poden recórrer (amb un bucle for) i es poden calcular unions, interseccions i diferències de conjunts.

La idea del tipus de dades conjunt és semblant a la de conjunt matemàtic: Es tracta d’una col·lecció (finita en aquest cas) d’elements sense repeticions. Com en matemàtiques, l’ordre dels elements en els conjunts en Python no és rellevant.

Usualment un conjunt comença buit i al llarg del programa se li insereixen i esborren elements. Alhora i, fonamentalment, es pot consultar si un valor qualsevol pertany o no al conjunt, sense modificar el conjunt. A més, a través del bucles for, es poden recórrer tots els elements d’un conjunt. I també es poden fer unions, interseccions i diferències de conjunts.

Aplicacions

El conjunt és una estructura de dades molt útil en informàtica: Per exemple, un navegador podria disposar d’un conjunt d’URLs potencialment perilloses i preguntar a l’usuari si realment hi vol entrar quan prova d’accedir-hi. També, una base de dades pot recuperar conjunts d’elements i calcular-ne interseccions, unions, diferències… En moltes ocasions, solucionar un problema consisteix a trobar un subconjunt dels elements d’un conjunt que tinguin una determinada propietat. Per tant, disposar d’una estructura de dades que representi conjunts sempre és útil.

Literals

La manera més senzilla d’escriure conjunts en Python és enumerant els seus elements entre claus i separant-los per comes. Aquí en teniu alguns exemples:

>>> vocals = {'a', 'e', 'i', 'o', 'u'}
>>> vocals
{'a', 'o', 'i', 'e', 'u'}
>>> nombres = {10, 20, 10, 30, 10, 20, 40, 50}
>>> nombres
{50, 20, 40, 10, 30}

Fixeu-vos que els conjunts no emmagatzemen elements repetits i que s’escriuen en un ordre arbitrari.

El conjunt buit, excepcionalment, no s’escriu {} sinó set() (perquè no es confongui amb el diccionari buit).

Funcions predefinides

Igual que per les llistes, Python ofereix algunes funcions predefinides sobre conjunts. Per exemple, la funció len, aplicada a un conjunt, en retorna el seu nombre d’elements (també dit cardinal):

>>> len({8, 3, 4, 5, 1})
5
>>> len(set())      # set() és el conjunt buit 
0
>>> len({66, 66})   # {66, 66} és el mateix que {66}
1

Les funcions min, max i sum aplicades sobre un conjunt en retornen el seu mínim, màxim i suma respectivament:

>>> min({8, 6, 3, 4, 6, 1})
1
>>> max({3.14, 2.78, 1.0})
3.14
>>> sum({3.14, 2.78, 1.0})
6.92

Operadors

La unió de dos conjunts es calcula amb l’operador |, la intersecció amb l’operador &, i la diferència amb l’operador -:

>>> {1, 2, 3} | {2, 3, 4}
{1, 2, 3, 4}
>>> {1, 2, 3} & {2, 3, 4}
{2, 3}
>>> {1, 2, 3} - {2, 3, 4}
{1}

Els operadors relacionals amb conjunts també funcionen, on <= expressa ⊂:

>>> {1} == {1, 1}
True
>>> {1} <= {1, 2}
True
>>> {1} >= {1, 2}
False

Com les llistes, els conjunts tenen un operador in que indica si un element es troba o no dins d’un conjunt. I l’operador not in retorna el contrari:

>>> "oca" in {"conill", "xai", "oca", "anec"}
True
>>> "gos" not in {"conill", "xai", "oca", "anec"}
True

Totes aquestes operacions sobre conjunts estan dissenyades per funcionar eficientment, en particular, molt més ràpidament que en llistes.

Afegir i treure elements

Els conjunts disposen de mètodes específcs per inserir-hi o esborrar-ne elements: El .add() afegeix un element i no té efecte si ja hi era. El .remove() treu un element i dóna un error si no hi era. El .discard() treu un element però no té efecte si no hi era. El .pop() elimina i retorna un element arbitrari d’un conjunt no buit.

>>> c = {10, 20, 30}
>>> c.add(40)
>>> c
{40, 10, 20, 30}
>>> c.add(40)
>>> c
{40, 10, 20, 30}
>>> c.remove(10)
>>> c
{40, 20, 30}
>>> c.remove(66)
KeyError: 66
>>> c.discard(66)
>>> c
{40, 20, 30}
>>> c.pop()
40
>>> c
{20, 30}

Afegir i treure elements amb aquestes operacions és també eficient.

Recórrer tots els elements d’un conjunt

Sovint, es vol recórrer tots els elements d’un cojunt, des del primer fins al darrer, realitzant alguna tasca amb cadascun d’aquests elements. Per exemple, per escriure cada element d’un conjunt es podria fer:

notes = {'do', 're', 'mi', 'fa', 'sol', 'la', 'si', 'do'}
for nota in notes:
    print(nota)

Aquí, el bucle for indica que la variable nota anirà prenent per valor cada element del conjunt notes de forma successiva. Dins del cos del bucle, cada valor és escrit. Compte: si bé es té la garantia de que tots els elements es visitaran, l’ordre en què es fa és indefinit. Avui aquest programa ha escrit

la
sol
mi
fa
re
do
si

però demà podria escriure les mateixes notes en qualsevols altre ordre.

Modificar un conjunt mentre s’està iterant sobre ell sol ser una mala idea. No ho feu.

El tipus conjunt

En Python, els conjunts són de tipus set, ho podem comprovar així:

>>> nombres = {10, 20, 30, 40, 50}
>>> type(nombres)
<class 'set'>

Per tal de comptar amb la seguretat que aporta la comprovació de tipus, d’ara en endavant suposarem que tots els elements d’un conjunt han de ser del mateix tipus: es diu que aquests conjunts són estructures de dades homegènies. Això no és cap imposició de Python, però és un bon costum per a novells.

En el sistema de tipus de Python, set[T] descriu un nou tipus que és un conjunt on cada element és de tipus T. Per exemple, set[int] és el tipus d’un conjunt d’enters i set[str] és un conjunt de textos.

En la majoria d’ocasions, no cal anotar els conjunts amb el seu tipus, perquè el sistema ja ho determina sol a través dels seus valors. Només en el cas de crear conjunts buits cal indicar el tipus dels elements de les llistes perquè, evidentment, el sistema no ho pot saber:

c1: set[int] = {40, 20, 34, 12, 40}    # no cal anotar el tipus: es dedueix automàticament
c2: set[float] = set()                 # cal anotar el tipus que tindrà el conjunt buit
                                       # perquè no es pot pas deduir

Un altre lloc on sempre cal anotar el tipus dels conjunt és quan es defineixen paràmetres:

def retorna_poder(jugador: str, daus: set[int]) -> float: 
    ...

Conversions

A vegades és útil convertir llistes en conjunts i viceversa:

>>> set([10, 20, 10])
{10, 20}
>>> set(range(10))
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> set('do re mi fa sol la si do'.split())
{'mi', 'do', 'si', 'la', 'fa', 'sol', 're'}
>>> list({10, 20, 30, 40})
[40, 10, 20, 30]

Conjunts per comprensió

Els conjunts també es poden escriure per comprensió de la mateixa manera que les llistes per comprensió. Aquest cop, però, cal usar claus enlloc de claudàtors:

>>> {2**n for n in range(9)}
{32, 1, 2, 64, 4, 128, 256, 8, 16}
>>> {str(i) for i in {2,3,4,5,6} if i % 2 == 0}
{'4', '6', '2'}
>>> n = 20
>>> {(a, b, c) for a in range(1, n + 1) for b in range(a, n + 1) for c in range(b, n + 1) if a**2 + b**2 == c**2}
{(6, 8, 10), (3, 4, 5), (8, 15, 17), (9, 12, 15), (5, 12, 13), (12, 16, 20)}

Els conjunts són objectes

Com les llistes, els conjunts també són objectes i, per tant, es manipulen a través de referències. Aquest codi ho demostra.

>>> c1 = {1, 2, 3}
>>> c1
{1, 2, 3}
>>> c2 = c1
>>> c2
{1, 2, 3}
>>> c1.add(4)
>>> c1
{1, 2, 3, 4}
>>> c2
{1, 2, 3, 4}

Es poden copiar conjunts fàcilment amb el mètode copy:

>>> c1 = {1, 2, 3}
>>> c2 = c1.copy()
>>> c1.add(4)
>>> c1
{1, 2, 3, 4}
>>> c2
{1, 2, 3}

Resum de les operacions bàsiques

operació significat
set() crea un conjunt buit.
{x1, x2, ...} crea un conjunt amb elements x1, x2, …
set(L) crea un conjunt amb els elements de la llista L.
len(s) retorna el cardinal del conjunt s.
s.add(x) afegeix l’element x al conjunt s.
s.erase(x) esborra l’element x del conjunt s (s’enfada si no hi és).
s.discard(x) esborra l’element x del conjunt s (no s’enfada si no hi és).
s.pop() elimina i retorna un element arbitrari d’s (s no pot ser buit).
s.copy() retorna una còpia independent d’s
x in s o x not in s diu si x és o no en s.
for x in s... itera sobre tots els elements del conjunt (en un ordre arbitrari). Mentre s’itera sobre un conjunt no es poden afegir/treure-li elements.
a | b retorna l’unió dels conjunts.
a & b retorna la intersecció dels conjunts.
a - b retorna la diferència dels conjunts.
a <= b indica si a és subconjunt de b.
a < b indica si a és subconjunt estricte de b.
set(L) retorna un conjunt amb tots els elements de la llista L.
list(s) retorna una llista amb els elements d’s en ordre arbitrari.




Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2022

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.