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

Question

我需要编写一个名为的函数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 importantprint(char_counts_subsets(char_counts))我怎样才能概括这个功能，以便它适用于任何cc字典？

Answer 1

这是一个组合问题，最好使用itertools.

from itertools import product

将每个字典项目扩展为一系列项目：

range_items = [[(x, z) for z in range(y + 1)] for x,y in char_counts.items()]

#[[('a', 0), ('a', 1)], [('b', 0), ('b', 1), ('b', 2)]]

将每个范围中的每个项目与所有其他范围中的每个项目进行笛卡尔积：

products = product(*range_items)

#[(('a', 0), ('b', 0)), (('a', 0), ('b', 1)),...(('a', 1), ('b', 2))]

消除具有 0 个计数器的对，并将剩余的转换为具有字典理解的字典：

[{k: v for k, v in pairs if v > 0} for pairs in products]

#[{}, {'b': 1}, {'b': 2}, {'a': 1}, {'a': 1, 'b': 1}, {'a': 1, 'b': 2}]

Answer 2

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

此外，就术语而言，char_counts基本上是一个多重集，输出与幂集非常相似，所以我猜你会称它为“幂多重集”。顺便说一句，查看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}]

Answer 3

没有 itertools，这对我有用。可能需要一些缩短，比如更好的获取密钥的方法。这是我无需查找任何内容即可完成此操作的最快方法。

def char_counts_subsets(cc):

    subset = []

    for key in cc:

        subset.append({key: cc[key]})

        if cc[key]!= 1:

            for i in range(1, cc[key]):

                subset.append({key: i})

    subset2 = []

    for i, item in enumerate(subset):

        for key in item:

            newitem = {key: item[key]}

            for item2 in subset:

                for key2 in item2:

                    if key != key2:

                        newitem.update({key2: item2[key2]})

                        if newitem not in subset2:

                            subset2.append(newitem)             

    subset.extend(subset2)

    return subset