以下问题更多是一种算法而不是代码挑战。
想象一下,我的数据结构如下:
cities = {'price' : ['malaga','berlin'],
'food' : ['milano','barcelona'],
'shopping': ['milano','barcelona'],
'weather' : ['barcelona','paris','lisabon','milano'],
'museums' : ['malaga','berlin','lisabon'],
'cafes' : ['paris','roma','lisabon'],
'kids' : ['milano','barcelona','paris','roma']}
在不同的城市可以找到很多特色。涵盖所有这些特征的最小城市数量是多少。也就是说,为了获得所有好处,我必须参观的城市数量最少。
到目前为止,我开始使用Counter
totals=[]
for key in cities.keys():
totals.append(cities[key])
totals_together = [city for cities in totals for city in cities]
totals_together
myCounter = Counter(totals_together)
print(myCounter.most_common())
到目前为止的结果:
[('milano', 4), ('barcelona', 4), ('paris', 3), ('lisabon', 3), ('malaga', 2), ('berlin', 2), ('roma', 2)]
myCounter给我提供了最佳城市的概念,但到目前为止还没有城市的最佳组合。从这里我可以得到第一个城市,获得特征,然后继续添加特征,直到一切都在那里。非常乏味。
应该有更好的方法。
我什至在考虑熊猫,但看不到熊猫会给这个问题带来什么。在我看来,这是一个非常普遍的问题。
注意:我什至没有在寻找这样的代码,仅欢迎有关如何解决该问题的想法。
注意2:请注意,可能存在一个或多个具有所有特征的城市,但在某些情况下(通常)可能没有一个城市具有所有特征。
因此,我要寻找的结果是:['milano','lisabon']假定此组合涵盖了所有特征。
一种前进的方法是创建所有组合(使用itertools),然后遍历它们并计算这些组合为您提供的活动。一旦找到可以进行所有活动的组合,就可以停止。
使用熊猫为您提供一种简单的方法来计算每个城市中可能进行的活动的数量。我相信您也可以没有。
import pandas as pd
import itertools
travel = {'price':['malaga','berlin'],
'food':['milano','barcelona'],
'shopping':['milano','barcelona'],
'weather':['barcelona','paris','lisabon','milano'],
'museums':['malaga','berlin','lisabon'],
'cafes':['paris','roma','lisabon'],
'kids':['milano','barcelona','paris','roma']}
# very ugly way to convert the travel into a data frame
# first we create a list of all cities
c = []
for activity in travel.keys():
for city in travel[activity]:
c.append(city)
c = set(c)
a = list(travel.keys())
df = pd.DataFrame(index=pd.Index(c, name='city'),
columns=pd.Index(a, name='activity'))
# then we set all city/activity crosspoints to True
for activity in travel.keys():
for city in travel[activity]:
df.loc[city, activity] = True
# and fill the rest with False
df = df.fillna(False)
# how many activities do we want to do?
all_activities = len(df.columns)
# let's store the results in a dictionary
results = {}
for combo_len in range(1, len(df.index)):
combos = list(itertools.combinations(df.index, combo_len))
for c in combos:
# print(f"Combo: {c}")
activity_count = df.query(f"city in {c}").any().sum()
results[c] = activity_count
if activity_count == all_activities:
print(f"{c}: {max_activities}")
break
else:
continue
break
尝试了所有组合后,或者找到包含所有活动的组合时,该代码将停止。
它提出的第一个可能的组合是:
('barcelona', 'paris', 'berlin'): 7
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句