我需要編寫一個名為的函數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字典？
3 回答
一只名叫tom的貓
TA貢獻1906條經驗 獲得超3個贊
這是一個組合問題，最好使用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}]
絕地無雙
TA貢獻1946條經驗 獲得超4個贊
我喜歡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}]
慕娘9325324
TA貢獻1783條經驗 獲得超4個贊
沒有 itertools，這對我有用?？赡苄枰恍┛s短，比如更好的獲取密鑰的方法。這是我無需查找任何內容即可完成此操作的最快方法。
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
添加回答
舉報
0/150
提交
取消