How To Generate All The Subsets Of A Counter?

I'm required to write a function named char_counts_subsets which takes a dictionary of character counts as parameter an returns all the subsets of this dictionary considering the v

Solution 1:

This is a combinatorial problem that is best solved using itertools.

from itertools import product

Expand each dictionary item into a range of items:

range_items = [[(x, z) for z inrange(y + 1)] for x,y in char_counts.items()]
#[[('a', 0), ('a', 1)], [('b', 0), ('b', 1), ('b', 2)]]

Take a Cartesian product of each item from the each range with each item from all other ranges:

products = product(*range_items)
#[(('a', 0), ('b', 0)), (('a', 0), ('b', 1)),...(('a', 1), ('b', 2))]

Eliminate the pairs that have 0 counters, and convert the leftovers into dictionaries with dict comprehensions:

[{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}]

Solution 2:

I like DYZ's answer, but I was wondering if it's possible to make it an efficient iterator. DYZ's range_items has a space complexity something like O(n+m), where n is the number of elements and m is the sum of their counts. My solution uses product on the ranges themselves, which I'm pretty sure is O(n).

Also, for terminology, char_counts is basically a multiset, and the output is very similar to a power set, so I guess you'd call it a "power multiset". BTW, check out collections.Counter, which is a multiset object in the standard library.

import itertools

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

    Output is an iterator of dicts.
    """
    elems = []
    ranges = []
    for elem, count insorted(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 countyield {e: c for e, c inzip(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}]

Solution 3:

without itertools, this works for me. May need a little shortening like a better way to get keys. This is the quickest way for me to do it without looking anything up.

defchar_counts_subsets(cc):subset= []
    for key in cc:subset.append({key:cc[key]})ifcc[key]!=1:foriinrange(1,cc[key]):subset.append({key:i})subset2= []
    fori,iteminenumerate(subset):for key in item:newitem= {key:item[key]}
            for item2 in subset:for key2 in item2:ifkey!=key2:newitem.update({key2:item2[key2]})if newitem not in subset2:subset2.append(newitem)subset.extend(subset2)returnsubset