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