Estructuras de datos en Python: Bolsas (bags)

Las bolsas o bags son contenedores similares a los conjuntos, pero permiten elementos duplicados. Son útiles para almacenar colecciones sin acceso individual.

En este artículo, aprenderás cómo implementar una bolsa en Python, incluyendo sus operaciones y características principales.

¿Qué es una bolsa o bag?

Una bolsa, también conocida como multiconjunto (multiset), es un contenedor similar a una bolsa de compras. Es una estructura semejante a un conjunto que permite múltiples instancias de un mismo valor. Las bolsas restringen el acceso a elementos individuales, lo que significa que no puedes acceder a un elemento específico por su posición.

Las características fundamentales de una bolsa incluyen las siguientes:

• Duplicados permitidos: A diferencia de un conjunto, puede contener múltiples copias del mismo valor.
• Sin orden definido: Los elementos no tienen un orden particular.
• Acceso restringido: No puedes acceder directamente a un elemento por su índice.

En Python, las bolsas no están integradas como una estructura de datos primitiva, pero puedes implementarla usando una lista como almacenamiento interno.

Operaciones comunes en una bolsa

A continuación, un resumen de las operaciones que soportará tu bolsa:

Implementación de una bolsa en Python

A continuación encontrarás la implementación de la bolsa en Python:

from collections import Counter
from collections.abc import Iterable, Iterator
from random import choice as _choice
from typing import Any, Optional

class Bag:
    """Implement a Bag (multiset) abstract data type."""

    def __init__(
        self, iterable: Optional[Iterable[Any]] = None, /
    ) -> None:
        self._data: list[Any] = []
        if iterable is not None:
            self._data.extend(iterable)

    def add(self, value: Any) -> None:
        """Add an object to the Bag."""
        self._data.append(value)

    def remove(self, value: Any) -> None:
        """Remove an object from the Bag."""
        try:
            self._data.remove(value)
        except ValueError:
            raise ValueError(
                f"{value} not in {self.__class__.__name__}"
            ) from None

    def count(self, value: Any) -> int:
        """Count the number of times an object appears in the Bag."""
        return self._data.count(value)

    def clear(self) -> None:
        """Remove all the objects from the Bag."""
        self._data.clear()

    def pop(self) -> Any:
        """Remove and return an item from the right end of the Bag."""
        try:
            return self._data.pop()
        except IndexError:
            raise IndexError("pop from empty bag") from None

    def randpop(self) -> Any:
        """Remove and return a random item from the Bag."""
        try:
            value: Any = _choice(self._data)
        except IndexError:
            raise IndexError("randpop from empty bag") from None
        self._data.remove(value)
        return value

    def as_counter(self) -> Counter:
        """Return a Counter from the objects in the Bag."""
        try:
            return Counter(self._data)
        except TypeError:
            raise

    def __len__(self) -> int:
        return len(self._data)

    def __contains__(self, value: Any) -> bool:
        return value in self._data

    def __iter__(self) -> Iterator:
        yield from self._data

    def __reversed__(self) -> Iterator:
        yield from reversed(self._data)

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({self._data})"

    __str__ = __repr__

El atributo ._data es una lista que almacena los elementos de la bolsa. Al permitir duplicados y no imponer un orden, las listas son una opción natural para esta estructura.

Los métodos principales te permiten ofrecer las siguientes funcionalidades:

• .add(): añade un elemento al final de la bolsa usando .append().
• .remove(): elimina la primera aparición de un elemento. Lanza ValueError si el elemento no existe.
• .count(): cuenta cuántas veces aparece un elemento en la bolsa.
• .clear(): elimina todos los elementos de la bolsa.
• .pop(): extrae el último elemento de la bolsa. Lanza IndexError si la bolsa está vacía.
• .randpop(): extrae un elemento aleatorio de la bolsa. Lanza IndexError si la bolsa está vacía.
• .as_counter(): devuelve un objeto Counter con las frecuencias de cada elemento. Lanza TypeError si algún elemento no es hashable.

Los métodos especiales te permiten ofrecer las siguientes funcionalidades:

• .__len__(): devuelve el número de elementos en la bolsa.
• .__contains__(): comprueba si un elemento está en la bolsa y devuelve True o False.
• .__iter__() y .__reversed__(): permiten iterar sobre los elementos de la bolsa en orden normal o inverso.
• .__repr__() y .__str__(): devuelven representaciones de cadena legibles.

Ejemplo de uso de la bolsa

En esta sección verás ejemplos prácticos de cómo crear y manipular instancias de tu clase Bag.

Inicialización

Para crear una Bag, puedes hacerlo sin argumentos o pasando un iterable. Observa que acepta elementos duplicados:

>>> from bag import Bag

>>> bag = Bag()
>>> bag
Bag([])

>>> bag = Bag([1, 2, 2, 3, 3, 3])
>>> bag
Bag([1, 2, 2, 3, 3, 3])

Añadir y eliminar elementos

Puedes añadir elementos y eliminarlos por su valor:

>>> from bag import Bag

>>> bag = Bag([1, 2, 3])
>>> bag.add(4)
>>> bag
Bag([1, 2, 3, 4])

>>> bag.remove(2)
>>> bag
Bag([1, 3, 4])

Si intentas eliminar un elemento que no existe, obtendrás un error:

>>> from bag import Bag

>>> bag = Bag([1, 2])
>>> bag.remove(99)
Traceback (most recent call last):
    ...
ValueError: 99 not in Bag

Contar elementos

El método .count() te permite saber cuántas veces aparece un elemento:

>>> from bag import Bag

>>> bag = Bag([1, 2, 2, 3, 3, 3])
>>> bag.count(1)
1
>>> bag.count(3)
3
>>> bag.count(99)
0

Extraer elementos

El método .pop() extrae el último elemento de la bolsa:

>>> from bag import Bag

>>> bag = Bag([1, 2, 3])
>>> bag.pop()
3
>>> bag
Bag([1, 2])

Longitud y pertenencia

Puedes consultar la longitud de la bolsa y verificar si un elemento está contenido en ella:

>>> from bag import Bag

>>> bag = Bag([1, 2, 2, 3])

>>> len(bag)
4

>>> 2 in bag
True
>>> 99 in bag
False

Obtener un contador de frecuencias

El método .as_counter() devuelve un objeto Counter con la frecuencia de cada elemento:

>>> from bag import Bag

>>> bag = Bag([1, 2, 2, 3, 3, 3])
>>> bag.as_counter()
Counter({3: 3, 2: 2, 1: 1})

Iteración

Los métodos .__iter__() y .__reversed__() permiten iterar sobre la bolsa tanto hacia adelante como hacia atrás:

>>> from bag import Bag

>>> bag = Bag([1, 2, 3])

>>> for item in bag:
...     print(item)
...
1
2
3

>>> for item in reversed(bag):
...     print(item)
...
3
2
1

Conclusión

Has aprendido cómo implementar una bolsa que permite almacenar elementos duplicados y proporciona operaciones como añadir, eliminar, contar frecuencias, extraer elementos aleatorios e iterar.

Este conocimiento te ayuda a comprender las diferencias entre bolsas y conjuntos, y a entender cuándo usar cada estructura según tus necesidades.