Как сгенерировать все подмножества счетчика? - PullRequest
Новая
       122

Как сгенерировать все подмножества счетчика?

1 голос
/ 14 июля 2020

Мне необходимо написать функцию с именем 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 словарем?

Ответы [ 3 ]

2 голосов
/ 14 июля 2020

Это комбинаторная задача, которую лучше всего решить, используя 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}]
1 голос
/ 15 июля 2020

Мне нравится ответ DYZ , но мне было интересно, можно ли сделать его эффективным итератором. DYZ range_items имеет пространственную сложность примерно как O (n + m), где n - количество элементов, а m - сумма их подсчетов. Мое решение использует product на самих range s, что, я уверен, равно 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}]
0 голосов
/ 16 июля 2020

без 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
...