How to generate all the subsets of a counter?

user_9608759 0
Viewed 139

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 values of character counts. An example code looks like this:

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

How can I generalize this function so that it will work with any cc dictionary?

itertools python-3.x dictionary python
3 Answers

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 in range(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}]
user_44929320

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

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}]
user_45183410

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.

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
user_139423800
Related