

In [1]:

    
"""
IPython Notebook v4.0 para python 2.7
Librerías adicionales: Ninguna.
Contenido bajo licencia CC-BY 4.0. Código bajo licencia MIT. (c) Sebastian Flores.
"""

# Configuracion para recargar módulos y librerías 
%reload_ext autoreload
%autoreload 2

from IPython.core.display import HTML

HTML(open("style/iwi131.css", "r").read())









    Out[1]:

IWI131

Programación de Computadores

Sebastián Flores

http://progra.usm.cl/

https://www.github.com/usantamaria/iwi131

¿Qué contenido aprenderemos?

Conjuntos y sus operaciones

¿Porqué aprenderemos ese contenido?

Conjuntos y sus operaciones

Porque muchos problemas pueden resolverse de manera extremadamente sencilla utilizando conjuntos.

¡Ahorre tiempo, aprenda conjuntos!

Motivación: letras en común

Escriba una función letras_en_comun(p,r) que retorne la cantidad de letras en común que tienen las palabras p y r.

Por ejemplo:

letras_en_comun('murcielago', 'gominola') debería regresar 6
letras_en_comun('protozoo', 'agasajada') debería regresar 0

Motivación: letras en común

Solución sólo con strings.

Poco intuitivo, ¿verdad?



In [ ]:

    
# Utilizando strings
def letras_en_comun(p, r):
    n = 0
    letras_a_revisar = p + r
    letras_vistas = ""
    for c in letras_a_revisar:
        if (c in p) and (c in r) and not (c in letras_vistas):
            n += 1
        letras_vistas += c 
    return n

## Verificación
print(letras_en_comun('murcielagoo', 'gominola')) # 6
print(letras_en_comun('protozoo', 'agasajada'))  # 0

Conjuntos

Conceptos

Se pueden definir mediante

{elemento_1, elemento_2, ..., elemento_n}

o bien

set(mi_lista)

Elementos de un conjunto puede ser cualquier objeto inmutable en python.
No existen repeticiones de elementos.
NO existe indexación ni orden en un conjunto.
NO CONFUNDIR CONJUNTOS CON DICCIONARIOS:

{"uno" : 1, "dos" : 2}

{"uno", 1, "dos", 2}

Conjuntos

Ejemplo



In [6]:

    
colores_1 = {'rojo', 'gris', 'azul', 'gris'}
colores_2 = set(['azul', 'gris', 'rojo', 'rojo', 'rojo'])
print colores_1
print colores_2
print colores_1==colores_2
#print colores_1[0] # Esto da error

print set('abracadabra')
print set(list('abracadabra'))
print set(['a', 'b', 'c', 'd', 'r', 'c', 'd', 'r'])









    



set(['rojo', 'azul', 'gris'])
set(['rojo', 'azul', 'gris'])
True
set(['a', 'r', 'b', 'c', 'd'])
set(['a', 'r', 'b', 'c', 'd'])
set(['a', 'c', 'b', 'r', 'd'])

Importante

set(mi_lista) regresa un nuevo objeto: el conjunto de los elementos no repetidos de la lista.
set(string) regresa el conjunto de las letras no repetidas del string.
Al aplicar set se obtiene un conjunto SIN orden de elementos y SIN elementos repetidos.



In [7]:

    
print set([1,2,1,2,3,4,3,2,1])
print set("abecedario")
print set(["aa","ab", "ba", "bb", "aa"])









    



set([1, 2, 3, 4])
set(['a', 'c', 'b', 'e', 'd', 'i', 'o', 'r'])
set(['aa', 'ab', 'ba', 'bb'])

Importante

En un conjunto no importa el orden, sino la pertenencia.

Operaciones en un conjunto:

Agregar y sacar elementos.
Verificar pertenencia
Recorrer un conjunto.
Número de elementos y operaciones de conjuntos.

Conjuntos

1. Agregar y sacar elementos del conjunto

Utilizar los métodos mi_conjunto.add(elemento) y mi_conjunto.remove(elemento)

2. Verificar pertenencia

Utilizar in



In [10]:

    
a = set() # conjunto vacio
a.add(19)
a.add(12)
a.add(8)
a.add(12)
print a # set([8, 19, 12])
a.remove(8)
print a # set([19, 12])

print 12 in a # True
print 8 in a # False









    



set([8, 19, 12])
set([19, 12])
True
False

Conjuntos

3. Operaciones básicas sobre conjuntos

Número de elementos: len(mi_set)
Intersección: mi_set_1 & mi_set_2
Unión: mi_set_1 | mi_set_2
Diferencia: mi_set_1 - mi_set_2
Subconjuntos propios: mi_set_1 < mi_set_2 o mi_set_1 > mi_set_2
Subconjuntos: mi_set_1 <= mi_set_2 o mi_set_1 >= mi_set_2



In [3]:

    
a = {1,2,3,4}
b = set(range(2,9,2))
c = set([2,4,8,16,32])
d = {2,3}
print "a=", a
print "len(a)=", len(a)
print "b=", b
print "len(b)=", len(b)
print "c=", c
print "len(c)=", len(c)
print "a&b=", a & b
print "a|b=", a | b
print "a-b=", a - b
#print "a+b=", a + b
print "a < a=", a < a
print "a <= a=", a <= a
print "d <= a=", d < a
print "a <= d=", a < d









    



a= set([1, 2, 3, 4])
len(a)= 4
b= set([8, 2, 4, 6])
len(b)= 4
c= set([8, 16, 2, 4, 32])
len(c)= 5
a&b= set([2, 4])
a|b= set([1, 2, 3, 4, 6, 8])
a-b= set([1, 3])
a < a= False
a <= a= True
d <= a= True
a <= d= False

Conjuntos

4. Utilizando ciclo for

Es posible utilizar ciclo for de manera directa sobre el conjunto.

(Pero no se podría utilizar un ciclo while! :)



In [16]:

    
# Funciona
colores = {"rojo", "verde", "rojo", "verde", "azul"}
for color in colores:
    print color, "es un bello color"









    



rojo es un bello color
azul es un bello color
verde es un bello color



In [20]:

    
# Da error
colores = {"rojo", "verde", "rojo", "verde", "azul"}
#colores = list(colores)
j=0
while j<len(colores):
    print colores[j], "es un bello color"
    j+=1









    



rojo es un bello color
azul es un bello color
verde es un bello color

Conjuntos

Ejemplos: Otras operaciones sobre conjuntos

Diferencia Simétrica de 2 conjuntos
Intersección de 3 conjuntos



In [21]:

    
a = {1,2,3,4}
b = set(range(2,9,2))
c = set([2,4,8,16,32])
print a
print b
print c
# Diferencia simetrica
print (b-a) | (a-b)
print (b|a) - (a&b)
# Interseccion de 3 conjuntos
print a&b&c









    



set([1, 2, 3, 4])
set([8, 2, 4, 6])
set([8, 16, 2, 4, 32])
set([8, 1, 3, 6])
set([8, 1, 3, 6])
set([2, 4])

Ejercicio: letras en común

Escriba una función letras_en_comun(p,r) que retorne la cantidad de letras (distintas) en común que tienen las palabras p y r.

Por ejemplo:

letras_en_comun('murcielago', 'gominola') debería regresar 6
letras_en_comun('protozoo', 'agasajada') debería regresar 0



In [22]:

    
# Utilizando diccionarios
def letras_en_comun(p, r):
    # Obtener el primer conjunto de letras
    p1 = set(p)
    # Obtener el segundo conjunto de letras
    r1 = set(r)
    # Intersectar los conjuntos
    interseccion = p1 & r1
    # Contar el número de elementos comunes
    return len(interseccion)

## Verificación
print(letras_en_comun('murcielagoo', 'gominola')) # 6
print(letras_en_comun('protozoo', 'agasajada'))  # 0

6
0

Solución: letras en común v1

Escriba una función letras_en_comun(p,r) que retorne la cantidad de letras en común que tienen las palabras p y r.



In [ ]:

    
# Utilizando conjuntos, versión extendida
def letras_en_comun(p, r):
    # Obtener el primer conjunto de letras
    A = set(p)
    # Obtener el segundo conjunto de letras
    B = set(r)
    # Intersectar los conjuntos
    C = A & B
    # Contar el número de elementos comunes
    n = len(C)
    return n

## Verificación
print(letras_en_comun('murcielagoo', 'gominola')) # 6
print(letras_en_comun('protozoo', 'agasajada'))  # 0

Solución: letras en común 2

Escriba una función letras_en_comun(p,r) que retorne la cantidad de letras en común que tienen las palabras p y r.



In [23]:

    
# Utilizando conjuntos, versión reducida
def letras_en_comun(p, r):
    return len(set(p) & set(r))

## Verificación
print(letras_en_comun('murcielagoo', 'gominola')) # 6
print(letras_en_comun('protozoo', 'agasajada'))  # 0

6
0

Ejercicio: elementos en común

Se tiene la siguiente lista de listas. ¿Cómo se puede conocer el número de elementos no repetidos?



In [25]:

    
def elementos(mis_listas):
    # FIX ME
    return
        
mi_lista = [ ["uno", "dos", "tres", "cuatro", "cinco"],
             ["dos", "cuatro", "seis", "ocho", "diez"],
             ["uno", "uno", "dos", "tres", "cinco", "ocho", "once"],
             # ...
           ]

#print set(mi_lista) # da error
print elementos(mi_lista) # Deberia dar 9









    



None



In [27]:

    
# Solución
def elementos(mis_listas):
    elementos = set()
    for lista in mis_listas:
        elementos = elementos | set(lista) # += , |=
        #elementos |= set(lista) # += , |=
    return elementos
        
mi_lista = [ ["uno", "dos", "tres", "cuatro", "cinco"],
             ["dos", "cuatro", "seis", "ocho", "diez"],
             ["uno", "uno", "dos", "tres", "cinco", "ocho", "once"],
             # ...
           ]

print elementos(mi_lista) # Deberia dar 9









    



set(['diez', 'seis', 'ocho', 'cuatro', 'cinco', 'dos', 'tres', 'once', 'uno'])

Ejercicio: elementos en común v2

Se tiene el siguiente diccionario.

¿Cómo se puede obtener una tupla con las llaves no repetidos?
¿Cómo se puede obtener una lista con los valores no repetidos?



In [29]:

    
d = {"uno":1, "one":1, "un":1,
     "dos":2, "two":2, "deux":2,
     "tres":3, "three":3, "trois":3,
     # ...
    }
# Tupla de llaves no repetidas
print tuple(set(d.keys()))
# Lista de valores no repetidos
print list(set(d.values()))









    



('trois', 'three', 'one', 'un', 'two', 'deux', 'dos', 'tres', 'uno')
[1, 2, 3]



In [ ]:

    
# Solución
d = {"uno":1, "one":1, "un":1,
     "dos":2, "two":2, "deux":2,
     "tres":3, "three":3, "trois":3,
     # ...
    }
# Tupla de llaves no repetidas
print tuple(set(d.keys())) # O directamente print tuple(d.keys()) 
                           #porque las llaves no pueden repetirse.
# Lista de valores no repetidos
print list(set(d.values()))

Ejercicio: elementos en común v3

Se tiene una lista de diccionarios de alumnos

¿Cómo se puede obtener los nombres no repetidos de los alumnos?



In [30]:

    
alumnos = [{"nombre":"Sebastian Flores", "rol":"2004001-7", 
            "ramos":["mate1", "progra", "fisica", "hum2"]},
           {"nombre":"Sebastian Fernandez", "rol":"2004002-8", 
            "ramos":["mate1", "progra2"]},
           {"nombre":"Maria Jose Vargas", "rol":"2004007-3", 
            "ramos":["mate1", "progra", "fisica", "hum1"]},
           {"nombre":"Cesar Moltedo", "rol":"2011001-4", 
            "ramos":["mate1", "progra", "progra2", "progra3"]},
           # ...
          ]



In [ ]:



In [31]:

    
# Nombres no repetidos solucion
nombres_set = set()
for alumno in alumnos:
    # Alumno es un diccionario
    nombre_completo = alumno["nombre"]
    nombre_pila = nombre_completo.split(" ")[0]
    nombres_set.add(nombre_pila)
    
print nombres_set









    



set(['Sebastian', 'Cesar', 'Maria'])

Ejercicio: elementos en común v3

Se tiene una lista de diccionarios de alumnos

¿Cómo se puede obtener todos los ramos cursados?



In [ ]:

    
alumnos = [{"nombre":"Sebastian Flores", "rol":"2004001-7", 
            "ramos":["mate1", "progra", "fisica", "hum2"]},
           {"nombre":"Sebastian Fernandez", "rol":"2004002-8", 
            "ramos":["mate1", "progra2"]},
           {"nombre":"Maria Jose Vargas", "rol":"2004007-3", 
            "ramos":["mate1", "progra", "fisica", "hum1"]},
           {"nombre":"Cesar Moltedo", "rol":"2011001-4", 
            "ramos":["mate1", "progra", "progra2", "progra3"]},
           # ...
          ]



In [ ]:

    
# Ramos no repetidos



In [ ]:

    
# Ramos no repetidos solucion
ramos_set = set()
for alumno in alumnos:
    # alumno es un diccionario
    lista_ramos = alumno["ramos"]
    ramos_set = ramos_set | set(lista_ramos)
    
print ramos_set

Ejercicio de Certamen: C2 2S 2013

El director técnico de la selección chilena le entrega como información una lista de tuplas con sus jugadores. Cada jugador viene representado por una tupla con la siguiente estructura: (nombre, informacion). A su vez, esta información es una tupla con la siguiente estructura: (posicion, goles, precio). Considere la siguiente estructura como ejemplo:



In [33]:

    
jugadores = [
             #(nombre,(posicion,goles,precio))
             ('Alexis Sanchez',('delantero',8,14000000)),
             ('Arturo Vidal',('central',3,4000000)),
             ('Claudio Bravo',('arquero',1,300000)),
             ('Gary Medel',('defensa',1,6000000)),
             ('Gonzalo Jara',('defensa',1,3000000)),
             ('Eugenio Mena',('defenda',0,5000000)),
             ('Miguel Pinto',('arquero',1,2000000)),
             ('Fabian Orellana',('delantero',3,4000000))
            ]

Ejercicio de C2 2S 2013

a) Implemente la función jugadores_por_posicion(posicion,jugadores), la cual recibe como parámetro un string con la posición y la lista de tuplas de jugadores. Esta función debe retornar un conjunto con los nombres de los jugadores que se desempeñan en dicha posición:

print jugadores_por_posicion('delantero',jugadores)
{'Alexis Sanchez', 'Fabian Orellana'}
print jugadores_por_posicion('defensa',jugadores)
{'Gary Medel', 'Gonzalo Jara'}
print jugadores_por_posicion('arquero',jugadores)
{'Claudio Bravo', 'Miguel Pinto'}



In [ ]:

    
def jugadores_por_posicion(posicion, jugadores):
    return

print jugadores_por_posicion('delantero',jugadores)
print jugadores_por_posicion('defensa',jugadores)
print jugadores_por_posicion('arquero',jugadores)



In [ ]:

    
def jugadores_por_posicion(posicion, jugadores):
    jugadores_en_posicion = set()
    for jugador, (pos, gol, precio) in jugadores:
        if pos==posicion:
            jugadores_en_posicion.add(jugador)
    return jugadores_en_posicion

print jugadores_por_posicion('delantero',jugadores)
print jugadores_por_posicion('defensa',jugadores)
print jugadores_por_posicion('arquero',jugadores)

Ejercicio de C2 2S 2013

b) Implemente la función cantidad_goles(nombre,jugadores), la cual recibe como parámetro un string con el nombre de un jugador y la lista de tuplas jugadores. Esta función debe retornar la cantidad de goles realizados por dicho jugador.

print cantidad_goles('Alexis Sanchez',jugadores)
8
print cantidad_goles('Eugenio Mena',jugadores)
0



In [ ]:

    
def cantidad_goles(nombre, jugadores):
    return

print cantidad_goles('Alexis Sanchez',jugadores)
print cantidad_goles('Eugenio Mena',jugadores)
print cantidad_goles('Sebastian Flores',jugadores)



In [34]:

    
def cantidad_goles(nombre, jugadores):
    for jugador, (pos, gol, precio) in jugadores:
        if jugador==nombre:
            return gol
    # Si llegamos aqui, no encontramos el nombre
    print nombre, "no esta en la seleccion Chilena."
    return 0

print cantidad_goles('Alexis Sanchez',jugadores)
print cantidad_goles('Eugenio Mena',jugadores)
print cantidad_goles('Sebastian Flores',jugadores)









    



8
0
Sebastian Flores no esta en la seleccion Chilena.
0

Ejercicio de C2 2S 2013

c) Implemente la función cantidad_goles_por_posicion(posiciones,jugadores), la cual recibe como parámetro un conjunto con las posiciones y la lista de tuplas jugadores. Este conjunto tiene la siguiente estructura:

posiciones = {'arquero','defensa','central','delantero'}

La función retorna un diccionario cuyas claves son las posiciones de los jugadores y su valor la cantidad total de goles realizados por jugadores que se desempeñan en dicha posici on.

posiciones = {'arquero','defensa','central','delantero'}
print cantidad_goles_por_posicion(posiciones,jugadores)
{'defensa': 2, 'arquero': 2, 'central': 3, 'delantero': 11}



In [39]:

    
def cantidad_goles_por_posicion(posiciones, jugadores):
    goles = {}
    for pos in posiciones:
        goles[pos] = 0
    for jugador, (pos, gol, precio) in jugadores:
        if pos in posiciones:
            goles[pos] += gol
    return goles

posiciones = {'defensa','central'}
print cantidad_goles_por_posicion(posiciones, jugadores)









    



{'central': 3, 'defensa': 2}



In [ ]:

    
def cantidad_goles_por_posicion(posiciones, jugadores):
    # Inicializar el diccionario vacio
    goles_por_posicion = {}
    for posicion in posiciones:
        goles_por_posicion[posicion] = 0
    # Llenar el diccionario
    for jugador, (pos, gol, precio) in jugadores:
        if pos in posiciones:
            goles_por_posicion[pos] += gol
    return goles_por_posicion

posiciones = {'arquero','defensa','central','delantero'}
print cantidad_goles_por_posicion(posiciones, jugadores)