我需要編寫(xiě)一個(gè)名為的函數(shù)char_counts_subsets，該函數(shù)將字符計(jì)數(shù)字典作為參數(shù)，并返回考慮字符計(jì)數(shù)值的該字典的所有子集。示例代碼如下所示：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))我怎樣才能概括這個(gè)功能，以便它適用于任何cc字典？
3 回答
一只名叫tom的貓
TA貢獻(xiàn)1906條經(jīng)驗(yàn) 獲得超3個(gè)贊
這是一個(gè)組合問(wèn)題，最好使用itertools.
from itertools import product
將每個(gè)字典項(xiàng)目擴(kuò)展為一系列項(xiàng)目：
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)]]
將每個(gè)范圍中的每個(gè)項(xiàng)目與所有其他范圍中的每個(gè)項(xiàng)目進(jìn)行笛卡爾積：
products = product(*range_items)
#[(('a', 0), ('b', 0)), (('a', 0), ('b', 1)),...(('a', 1), ('b', 2))]
消除具有 0 個(gè)計(jì)數(shù)器的對(duì)，并將剩余的轉(zhuǎn)換為具有字典理解的字典：
[{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}]
絕地?zé)o雙
TA貢獻(xiàn)1946條經(jīng)驗(yàn) 獲得超4個(gè)贊
我喜歡DYZ 的回答，但我想知道是否有可能使它成為一個(gè)高效的迭代器。DYZ 的range_items空間復(fù)雜度類(lèi)似于 O(n+m)，其中n是元素的數(shù)量，m是它們的計(jì)數(shù)之和。product我的解決方案在s 本身上使用range，我很確定它是 O(n)。
此外，就術(shù)語(yǔ)而言，char_counts基本上是一個(gè)多重集，輸出與冪集非常相似，所以我猜你會(huì)稱(chēng)它為“冪多重集”。順便說(shuō)一句，查看collections.Counter，這是標(biāo)準(zhǔn)庫(kù)中的一個(gè)多集對(duì)象。
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貢獻(xiàn)1783條經(jīng)驗(yàn) 獲得超4個(gè)贊
沒(méi)有 itertools，這對(duì)我有用。可能需要一些縮短，比如更好的獲取密鑰的方法。這是我無(wú)需查找任何內(nèi)容即可完成此操作的最快方法。
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
添加回答
舉報(bào)
0/150
提交
取消