python - 查找列表字典的值的最佳组合(可能使用 Pandas )

Question

以下问题与其说是代码挑战，不如说是一种算法。
想象一下，我有一个如下的数据结构:

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']}

在不同的城市中可以找到许多特征。
涵盖所有这些特征的最少城市数量是多少？ IE。为了获得所有好处，我必须访问的城市数量最少。
到目前为止，我开始使用 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 为我提供了最佳城市的概念，但到目前为止还不是城市的最佳组合。
从这里我可以得到第一个城市，得到特征，然后继续添加特征，直到全部都存在。很乏味。
应该有更好的方法。
我什至在考虑 Pandas ，但看不出 Pandas 会为这个问题带来什么。
这在我看来是一个很常见的问题。
注意:我什至不是在寻找这样的代码，只是关于如何解决问题的想法非常受欢迎。
注2:请注意，可能存在一个或多个具有所有特征的城市，但可能存在(通常)没有具有所有特征的单个城市的情况。
所以我正在寻找的结果是:
['milano','lisabon'] 假设这个组合涵盖了所有特征。

Answer 1

一种方法是创建所有组合(使用 itertools)，然后遍历它们并计算这些组合为您提供的事件。一旦你找到了一个可以为你提供所有事件的组合，你就可以停止。
使用 pandas 为您提供了一种计算每个城市可能事件数量的简单方法。我相信你也可以不用。

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