带有重复/重复元素的Python“集合”

Question

是否存在表示可以包含重复元素的“集合”的标准方法。

据我所知，一个集合恰好具有一个元素的一个或零。我希望功能可以有任意数量。

我目前正在使用一个字典，其中元素作为键，数量作为值，但是由于许多原因，这似乎是错误的。

动机：我相信此类集合有很多应用程序。例如，对喜欢的颜色的调查可以表示为：调查= ['蓝色'，'红色'，'蓝色'，'绿色']

这里，我不在乎订单，但在乎数量。我想做类似的事情：

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

...甚至可能

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

注意：是的，集合不是此类集合的正确术语。有没有更正确的一个？

当然可以使用一个列表，但是所需的集合是无序的。更不用说为我命名集合的方法似乎更合适。

Answer 1

您正在寻找multiset。

Python最接近的数据类型是collections.Counter：

collections.Counter是用于计算可哈希对象的Counter子类。它是一个无序集合，其中元素存储为字典键和它们的计数存储为字典值。允许计数任何包含零或负计数的整数值。 dict类与其他语言的袋或多件套类似。

对于多集的实际实现，请使用pypi上数据结构包中的Counter类。请注意，这仅适用于Python 3。如果您需要Python 2，bag是为Python 2.4编写的bag的配方。

Answer 2

您对带有元素/计数的字典的方法对我来说似乎还可以。您可能需要更多功能。看看here。

• O（1）测试元素是否存在以及当前计数检索（比使用bag和collections.Counter更快）
• [collections.Counter看起来像一个包含所有重复项的列表
• 易于操作的合并/与其他计数器的区别

Answer 3

您可以使用普通的element in list并在需要访问元素的“数量”时使用list.count(element)。

counter.elements()

Answer 4

另一个Python多集实现使用排序列表数据结构。在PyPI上有几个实现。一种选择是list模块，该模块实现list.count(element)数据类型，该数据类型有效地实现类似

my_list = [1, 1, 2, 3, 3, 3]

my_list.count(1) # will return 2

，sortedcontainers和SortedList的集合式方法。 sortedcontainers模块以纯Python，快速C实现（甚至更快）实现，具有100％的单元测试覆盖率和数小时的压力测试。

从PyPI安装很容易：

add

如果无法remove，则只需从contains下拉sortedlist.py文件。

按原样使用它：

pip install sortedcontainers

sortedcontainers模块还与其他流行的实现一起维护pip install。

Answer 5

您正在寻找的确实是一个open-source repository（或bag），一个不一定是不同元素的集合（而set不包含重复项）。

这里有一个多集实现：

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

（Pypy的performance comparison模块）。

多集的数据结构称为multiset。 https://github.com/mlenzen/collections-extended是collections extended模块中bag类的子类，带有一个额外的字典，用于跟踪元素的多重性。

bag

Set的一种好方法是collections（类似于列表的

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)

），由于每个元素的出现次数始终保持在包的最新状态，因此可以快速返回所有元素的多重性字典：

bag

Answer 6

带有重复/重复元素的Python“设置”

这取决于您如何定义集合。可以假设对OP

1. 顺序无关紧要（无论是有序还是无序）
2. 允许重复/重复的元素（也称为multiplicites）

基于这些假设，选项减少为两种抽象类型：nlargest或Counter。在Python中，这些类型通常分别转换为

>>> 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}) 

和list。请参阅“细节”以了解一些细节。

给出

multiset

代码

复制元素列表：

list

复制元素的“多重集”：

Counter

---

详细信息

关于数据结构

[这里我们混合了一些术语，很容易混淆。为了澄清，这里是一些基本的数学数据结构，与Python中的数据结构相比。

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]

从表中可以推断出每种类型的定义。示例：set是一个忽略顺序并拒绝重复元素的容器。相反，list是保留顺序并允许复制元素的容器。

也可以从表中看到：

• 有序集和多集都没有在Python中显式实现
• “顺序”是元素随机排列的相反术语，例如排序或插入顺序
• 集和多集不是严格排序的。它们可以被排序，但是顺序无关紧要。
• 多集允许重复，因此它们不是严格的集（术语“

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

  ”的确是

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

  ）。

关于多重集

[有些人可能会说

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)

是一个多集。在许多情况下，可以安全地对待它，但是请注意，set只是key-multiplicity对的字典（映射）。这是一幅多重图。请参见展平的多集中元素的示例：

confusing

注意，有些残留的排序，如果您期望结果混乱，可能会令人惊讶。但是，无序并不排除秩序。因此，尽管您可以从collections.Counter生成多集，但请注意以下有关Python残差排序的规定：

• 重复项在映射中分组在一起，引入了一定程度的顺序
• 在Python 3.6中，字典的保留插入顺序

摘要

在Python中，可以将多重集转换为多重映射，即Counter，它不会像纯集合那样随机无序。可能会有一些剩余排序，在大多数情况下都可以，因为在多集中排序通常并不重要。

另请参见>>

• 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]

  -Counter中其他数据类型的包>

  ^{*数学上，（根据Counter，我们用花括号collections-extended表示集合，用括号collections-extended表示列表，如Python所示。与Python不同，逗号collections表示顺序。}

如果需要重复，请使用列表，并在需要作为集合操作时将其转换为集合。

Answer 7

如果需要重复，请使用列表，并在需要作为集合操作时将其转换为集合。