时间戳

首页 > 解决方案 > 如何生成计数器的所有子集？

python - 如何生成计数器的所有子集？

问题描述

我需要编写一个名为的函数，该函数char_counts_subsets将字符计数字典作为参数，并考虑字符计数的值返回该字典的所有子集。示例代码如下所示：

char_counts = {"a": 1, "b": 2}

def char_counts_subsets(cc):
    return [{},
            {"b": 1}, {"b": 2}, {"a": 1},
            {"a": 1, "b": 1}, {"a": 1, "b": 2}
            ] # ordering of the subsets isn't important

print(char_counts_subsets(char_counts))

我怎样才能概括这个函数，以便它可以与任何cc字典一起使用？

标签： pythonpython-3.xdictionaryitertools

解决方案

我喜欢DYZ 的回答，但我想知道是否有可能使它成为一个高效的迭代器。DYZ 的range_items空间复杂度类似于 O(n+m)，其中n是元素的数量，m是它们的计数之和。我的解决方案product在ranges 上使用，我很确定是 O(n)。

另外，就术语而言，char_counts它基本上是一个multiset ，并且输出与power set非常相似，所以我猜你会称之为“power multiset”。顺便说一句，签出collections.Counter，这是标准库中的一个多集对象。

import itertools

def power_multiset(multiset):
    """
    Generate all sub-multisets of a given multiset, like a powerset.

    Output is an iterator of dicts.
    """
    elems = []
    ranges = []
    for elem, count in sorted(multiset.items()):
        elems.append(elem)
        ranges.append(range(count+1))

    for sub_counts in itertools.product(*ranges):
        # "if c" filters out items with a 0 count
        yield {e: c for e, c in zip(elems, sub_counts) if c}

>>> char_counts = {"a": 1, "b": 2}
>>> list(power_multiset(char_counts))
[{}, {'b': 1}, {'b': 2}, {'a': 1}, {'a': 1, 'b': 1}, {'a': 1, 'b': 2}]

推荐阅读