#!/usr/bin/env python################################################################################ Conjuntos# Modulo que define funciones para trabajar con conjuntos.# Copyright (C) %Y Juan Riquelme a.k.a Soulchainer (J.R.G)# <soulchainer@soulchainer.net>###############################################################################def lista_a_conjunto(lista): """ Devuelve un conjunto (que es una lista) con los mismos elementos que hay en lista, pero sin repetición. Devuelve None si la lista es vacia. """ # Tratamos el caso de la lista (y por tanto también el conjunto) sea vacia if not lista: return None # Creamos una copia de lista y la ordenamos conjunto = lista[:] conjunto.sort() # Posición actual y indice máximo la lista (pos, tope) = (1, len(conjunto) -1) # Recorremos la lista ordenada y borramos de la lista cada elemento que sea # igual que el anterior while pos <= tope: if conjunto[pos] == conjunto[pos -1]: del conjunto[pos] tope -= 1 else: pos += 1 return conjuntodef union(a, b): """ Devuelve el conjunto (lista) resultante de unir los conjuntos a y b. """ # Tratamos el caso de que algun conjunto sea vacio if not a and not b: return None elif not a: return b elif not b: return a # Unimos los conjuntos, ordenamos el resultante y eliminamos repetidos u = a + b return lista_a_conjunto(u)def interseccion(a, b): """ Devuelve el conjunto (lista) cuyos elementos pertenecen a a y b """ # Tratamos el caso de que algun conjunto sea vacio if not a or not b: return None n = a + b n.sort() # Posición actual y indice máximo la lista (pos, tope) = (0, len(n) -1) while pos < tope: # Si el elemento actual está repetido, avanzamos y borramos el repetido. # Si no está repetido (no está en los 2 conjuntos), tb lo borramos # Así obtenemos 1 conjunto con los elementos que están en ambos. if n[pos] == n[pos +1]: pos += 1 del n[pos] tope -= 1 if pos < len(n): del n[pos] return ndef diferencia(a, b): """ Devuelve el conjunto (lista) cuyos elementos estan en a pero no en b """ # Tratamos el caso de que algun conjunto sea vacio if not a: return None elif not b: return a dif = a[:] dif.sort() # Obtener los elementos que están en a y no en b es lo mismo que obtener los # elementos que están en ambos y eliminarlos de a n = interseccion(a, b) indice = 0 for i in n: # En cada iteración, actualizamos el indice aplicando la funcion index() # a la subsecuencia de a empezando por el indice del elemento anterior # encontrado, para agilizar la ejecución de la función index indice += dif[indice:].index(i) del dif[indice] return difdef iguales(a, b): """ Devuelve True si ambos conjuntos son iguales y False si no lo son """ # Tratamos el caso de que algun conjunto sea vacio if not a: return not b elif not b: return False a.sort() b.sort() return a == b