Python «set» con duplicados/elementos repetidos

Hay una forma estándar de representar un «conjunto» que puede contener elementos duplicados.

Como yo lo entiendo, un conjunto tiene exactamente un cero o de un elemento. Quiero funcionalidad para tener cualquier número.

Actualmente estoy usando un diccionario con elementos como claves, y la cantidad de valores, pero esto parece mal por muchas razones.

Motivación:
Yo creo que hay muchas aplicaciones para la colección. Por ejemplo, una encuesta de colores favoritos podría ser representado por:
encuesta = [‘azul’, ‘rojo’, ‘azul’, ‘verde’]

Aquí, no me importa el orden, pero yo acerca de las cantidades. Quiero hacer cosas como:

survey.add('blue')
# would give survey == ['blue', 'red', 'blue', 'green', 'blue']

…y tal vez incluso

survey.remove('blue')
# would give survey == ['blue', 'red', 'green']

Notas:
Sí, no es el término correcto para este tipo de colección. Hay una más correcta?

Una lista de curso iba a funcionar, pero la colección se requiere es desordenada. Por no mencionar que el método de nomenclatura para los conjuntos a mí me parece ser la más apropiada.

  • Podría ayudar explicando por qué quieres hacer esto.
  • Si necesita duplicados no es un set por definición. Puede usted demostrar lo que cree que quiere, y tal vez nos puede sugerir un recipiente adecuado o el tipo de datos?
  • Este es contradictoria solicitud a menos que usted aclarar su intención. Técnicamente podría definir un custom hash método para sus objetos de permitir duplicados en un conjunto o dict pero entonces sería usted de contar de otra manera. Yo no creo que usted realmente desea duplicar los miembros si su objetivo es contar. Dict con valor de recuento, no parece mal por muchas razones.
  • Si el orden no es importante para usted, el hecho de que la lista está ordenada no debería ser un problema para usted. ¿Hay alguna razón usted necesita para cambiar aleatoriamente el orden?
  • Si el OP rewords su pregunta, sería mucho mejor. Es suficiente para pedir una estructura que «soporta múltiples elementos idénticos»; pidiendo diferentes nombres de método y de la falta de orden no es razonable. La lista no es una buena solución, ya que es una pérdida de memoria cuando cada elemento se repite muchas veces, y una pérdida de tiempo en insertar/eliminar comparación con el conjunto múltiple.
  • La belleza de desbordamiento de la pila es que a veces usted no sabe lo que usted no sabe. Si yo sabía lo que «debería» han estado preguntando, yo podría haber sido capaz de google. La capacidad de un ser humano para entender lo que se necesita es la razón por la que finalmente se pregunte desbordamiento de la pila después de infructuosos tiempo dedicado a googlear. Espero que esta reacción hacia la educación de las personas en busca de ayuda no prevalecerán sobre la decencia común. JSpolsky habló de la importancia de la comunidad aquí, y yo no puedo ayudar pero siento que algo va mal.
  • En «Notas», creo que el término que el OP se busca es bag (un término común para multiset)

InformationsquelleAutor cammil | 2012-04-16

7 Kommentare

  1. 34

    Usted está buscando un conjunto múltiple.

    Python más cercano del tipo de datos es colecciones.Counter:

    Un Counter es un dict subclase para contar hashable objetos. Es un
    colección desordenada donde los elementos se almacenan como diccionario de claves y
    su cuenta se almacenan como diccionario de valores. Los recuentos se permite
    cualquier valor entero, incluyendo el cero o negativo de la cuenta. La Counter clase
    es similar a las bolsas o multisets en otros idiomas.

    Para una implementación real de un conjunto múltiple, utilice el bolsa clase a partir de las estructuras de datos del paquete en pypi. Tenga en cuenta que esto es para Python 3. Si usted necesita Python 2, aquí es una receta para un bag escrito para Python 2.4.

    • ¿Cuál es la diferencia entre las colecciones.Contador y pypi de la bolsa?
    • En python 2.7.6 puedo ejecutar la bolsa, ¿por qué?
    • Uno de los grandes gotcha aquí: len(counter_obj) le da el número de elementos únicos, pero no el número total de elementos como se puede esperar de un conjunto múltiple. Pero, usted puede hacer todas las otras operaciones como la de los sindicatos y de las intersecciones al igual que se hace con conjuntos.
    • Buen punto. Para el número total de elementos sum(counter_obj.values()).
  2. 14

    Su enfoque con dict con elemento/conde parece bien a mí. Usted probablemente necesita más funcionalidad. Eche un vistazo a colecciones.Counter.

    • O(1) comprobar si un elemento está presente y el recuento actual de recuperación (más rápido que con element in list y list.count(element))
    • counter.elements() parece una lista con todos los duplicados
    • fácil manipulación de la unión/la diferencia con otros Contadores
  3. 0

    Puede utilizar un simple list y uso list.count(element) siempre que quiera acceder a la «cantidad» de los elementos.

    my_list = [1, 1, 2, 3, 3, 3]
    
    my_list.count(1) # will return 2
  4. 0

    Una alternativa de Python conjunto múltiple aplicación utiliza una lista ordenada estructura de datos. Hay un par de implementaciones en PyPI. Una opción es el sortedcontainers módulo que implementa un SortedList tipo de datos que implementa de manera eficiente set-como métodos como add, remove, y contains. El sortedcontainers módulo se implementa en puro Python, rápido-como-C implementaciones (aún más rápido), tiene el 100% de la unidad de la cobertura de las pruebas, y las horas de las pruebas de estrés.

    Instalación es fácil desde PyPI:

    pip install sortedcontainers

    Si usted no puede pip install, a continuación, simplemente tire de la sortedlist.py archivo de la abrir-repositorio de código fuente.

    Usarlo como si fuera un conjunto:

    from sortedcontainers import SortedList
    survey = SortedList(['blue', 'red', 'blue', 'green']]
    survey.add('blue')
    print survey.count('blue') # "3"
    survey.remove('blue')

    La sortedcontainers módulo también mantiene una comparación de rendimiento con otros populares implementaciones.

  5. 0

    Lo que estás buscando es, de hecho, un conjunto múltiple (o bolsa de), una colección de no necesariamente distintos elementos (mientras que un conjunto no contiene duplicados).

    Hay una aplicación para multisets aquí: https://github.com/mlenzen/collections-extended (Pypy del colecciones extendida módulo).

    La estructura de datos para multisets se llama bag. Un bag es una subclase de la Set clase de collections módulo con un extra de diccionario de seguir la pista de las multiplicidades de los elementos.

    class _basebag(Set):
        """
        Base class for bag and frozenbag.   Is not mutable and not hashable, so there's
        no reason to use this instead of either bag or frozenbag.
        """
        # Basic object methods
    
        def __init__(self, iterable=None):
            """Create a new basebag.
    
            If iterable isn't given, is None or is empty then the bag starts empty.
            Otherwise each element from iterable will be added to the bag
            however many times it appears.
    
            This runs in O(len(iterable))
            """
            self._dict = dict()
            self._size = 0
            if iterable:
                if isinstance(iterable, _basebag):
                    for elem, count in iterable._dict.items():
                        self._inc(elem, count)
                else:
                    for value in iterable:
                        self._inc(value)

    Un buen método para bag es nlargest (similar a Counter para las listas), que devuelve el multiplicidades de todos los elementos de manera extremadamente rápida, ya que el número de ocurrencias de cada elemento se mantiene actualizada en la bolsa del diccionario:

    >>> b=bag(random.choice(string.ascii_letters) for x in xrange(10))
    >>> b.nlargest()
    [('p', 2), ('A', 1), ('d', 1), ('m', 1), ('J', 1), ('M', 1), ('l', 1), ('n', 1), ('W', 1)]
    >>> Counter(b)
    Counter({'p': 2, 'A': 1, 'd': 1, 'm': 1, 'J': 1, 'M': 1, 'l': 1, 'n': 1, 'W': 1}) 
  6. 0

    Python «set» con duplicados/elementos repetidos

    Esto depende de cómo se defina un conjunto. Uno puede suponer que a la OP

    1. no importa el orden (si ordenadas o no)
    2. replica/elementos repetidos (un.k.una. multiplicites) se permite

    Dados estos supuestos, las opciones se reducen a dos tipos abstractos: una lista o un conjunto múltiple. En Python, este tipo suelen traducir a un list y Counter respectivamente. Ver los Detalles en algunas sutilezas a observar.

    Dado

    import random
    
    import collections as ct
    
    random.seed(123)
    
    
    elems = [random.randint(1, 11) for _ in range(10)]
    elems
    # [1, 5, 2, 7, 5, 2, 1, 7, 9, 9]

    Código

    Una lista de replicar elementos:

    list(elems)
    # [1, 5, 2, 7, 5, 2, 1, 7, 9, 9]

    Un «conjunto múltiple» de replicar elementos:

    ct.Counter(elems)
    # Counter({1: 2, 5: 2, 2: 2, 7: 2, 9: 2})

    Detalles

    En Estructuras De Datos

    Tenemos una mezcla de los términos que aquí, que fácilmente se confunde. Para aclarar, aquí están algunos matemáticos básicos de estructuras de datos en comparación con aquellos en Python.

    Type        |Abbr|Order|Replicates|   Math*   |   Python    | Implementation
    ------------ | ---- | ----- | ---------- | ----------- | ------------- | ----------------
    Set         |Set |  n  |     n    | {2  3  1} |  {2, 3, 1}  | set(el)
    Ordered Set |Oset|  y  |     n    | {1, 2, 3} |      -      | list(dict.fromkeys(el)
    Multiset    |Mset|  n  |     y    | [2  1  2] |      -      | <see `mset` below>
    List        |List|  y  |     y    | [1, 2, 2] |  [1, 2, 2]  | list(el)

    De la tabla, se puede deducir de la definición de cada tipo. Ejemplo: un conjunto es un contenedor que hace caso omiso de la orden y rechaza replicar elementos. En contraste, un lista es un recipiente que conserva el orden y permite replicar los elementos.

    También de la tabla, podemos ver:

    • Tanto un conjunto ordenado y un conjunto múltiple no son explícitamente implementado en Python
    • «Orden» es un contrario plazo a una disposición aleatoria de los elementos, por ejemplo, ordenan o orden de inserción
    • Conjuntos y multisets no son estrictamente ordenada. Que puede ser ordenado, pero no importa el orden.
    • Multisets permiso de replica, por lo que no son estrictas conjuntos (el término «conjunto» es, de hecho,confuso).

    En Multisets

    Algunos pueden argumentar que collections.Counter es un conjunto múltiple. Usted está seguro en muchos casos a tratar como tal, pero ser conscientes de que Counter es simplemente un diccionario (mapeo) de la clave-multiplicidad pares. Es un mapa de multiplicidades. Ver un ejemplo de los elementos en el plano conjunto múltiple:

    mset = [x for k, v in ct.Counter(elems).items() for x in [k]*v]
    mset
    # [1, 1, 5, 5, 2, 2, 7, 7, 9, 9]

    Notar que hay algunos residual de pedido, que puede ser sorprendente si se espera desordenada resultados. Sin embargo, el desorden no excluye la orden. Así, si bien se puede generar un conjunto múltiple de una Counter, ser conscientes de los siguientes supuestos restos de pedidos en Python:

    • replica obtener agrupados en la asignación, la introducción de un cierto grado de orden
    • en Python 3.6, dict es preservar el orden de inserción

    Resumen

    En Python, un conjunto múltiple puede ser traducido a un mapa de multiplicidades, es decir, un Counter, que no es al azar desordenada como un puro conjunto. Puede haber algún residuo de pedidos, que en la mayoría de los casos es aceptar ya que el orden no importa en multisets.

    Ver También

    *Matemáticamente, (de acuerdo a N. Wildberger, expresamos llaves {} implica un conjunto y soportes [] implicar una lista, como se ve en Python. A diferencia de Python, comas , implicar orden.

  7. -2

    Si necesita duplicados, el uso de una lista, y transformarla en un conjunto cuando usted necesita funcionar como un conjunto.

    • Lo más probable es que el OP estaba buscando un conjunto múltiple, y la transformación de una lista a un conjunto pierde duplicados.
    • He publicado esta respuesta antes de que fuera editado. Mi enfoque es utilizar sólo el conjunto como una vista de la lista original.

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea