根据字典值获取不同的集合

Question

我在解决一个编码难题时遇到了一些需要帮助的问题

问题基本上是问一个人在不完全赤裸的情况下可以穿多少种衣服，输入的衣服类型是多少。请允许我详细说明：

输入：

hat headgear
sunglasses eyewear
cap headgear

输出：

5

本例中输出为5的原因是因为可能的组合是(hat)、(sunglasses)、(cap)、(hat, sunglasses)、(cap, sunglasses)，因为每个类别只允许穿一件

我最初的想法是根据它们的值对每个项目进行分类，键是特定的项目，然后使用itertools.product找出有多少种可能的组合

有没有办法从{'hat': 'headgear', 'cap': 'headgear', 'sunglasses': 'eyewear'}中提取[hat, cap]，[sunglasses]

谢谢

Answer 1

我将创建另一个字典，其中服装类型是关键，包含该类型所有服装的列表是值：

clothes = {}
for wearable, clothing_type in your_dict:
    if clothing_type not in clothes:
        clothes[clothing_type] = ['']
    clothes[clothing_type].append(wearable)
# now clothes is {'headgear': ['', 'hat', 'cap'], 'eyewear': ['', 'sunglasses']}

如果只需要数字5，现在可以将每个列表的长度相乘，然后减去1：

possible_combinations = 1
for clothing_type, wearables in clothes:
    possible_combinations *= len(wearables)
possible_combinations -= 1
# 5

如果您想要实际的组合，itertools是一个非常好的主意：

combinations = [list(c) for c in itertools.product(*clothes.values())]
for combination in combinations:
    combination.remove('')
combinations = [c for c in combinations if c]

print(combinations)

输出：

[['sunglasses'], ['hat'], ['hat', 'sunglasses'], ['cap'], ['cap', 'sunglasses']]

Answer 2

您可以首先将项存储在字典中，其中键表示项的类型，值作为每种类型的特定项的列表。例如：

gear = {
    'headgear': ['hat', 'cap', 'bandana'],
    'eyewear': ['sunglasses'],
    'footwear': ['socks', 'shoes']
}

然后你可以按照你最初的方法，找到每种类型衣服的长度1或更多的组合（例如(headgear,), (headgear, eyewear)等）。这将使您能够计算每个档位组合可实现的特定组合数，您可以将其累积为总和

例如，对于上述字典中的齿轮组合('headgear', 'eyewear')，特定组合的总数为len(gear['headgear']) * len(gear['eyewear'])，即3。对于组合('headgear', 'eyewear', 'footwear')，它是3 * 1 * 2 = 6。我们的最终结果是所有可能长度大于1的组合的所有这些数字的总和。这为我们提供了以下代码：

from itertools import combinations
from functools import reduce

res = 0
for num_gears in range(1, len(gear) + 1):
    for gear_combination in combinations(gear.keys(), num_gears):
        res += reduce(lambda a, c: a * c, [len(gear[c]) for c in gear_combination])

print(res) # 23

Answer 3

我想你让你的生活变得很艰难。 如果你不需要知道所有的衣服，你可以为它设置数字：你可以戴帽子，帽子或什么都不戴在头上，所以让头饰的数字=3，眼镜是2（太阳镜或什么都没有）等等。为此，您可以从字符串字典开始，int with string是可穿戴的类型，int是元素数加1。 最后，你只需将数字相乘，在字典中穿行，取1表示完全赤身裸体