找到列表字典值的最佳组合（可能 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。为了获得所有好处，我必须访问的城市数量最少。

到目前为止我开始使用计数器

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

Answer 2

这实际上类似于组合求和问题，但是您需要的不是目标求和，而是集合并集的长度。

首先重塑你的cities:

from collections import defaultdict

d = defaultdict(set)

for k, v in cities.items():
    for city in v:
        d[city].add(k)

print (d)

#defaultdict(<class 'set'>, {'malaga': {'price', 'museums'}, 'berlin': {'price', 'museums'}, ...})

现在您可以应用具有唯一值的组合求和逻辑，但请改用 len：

def find_cities(candidates, target):
    ans = set()
    def dfs(cur, start):
        if cur:
            num = len(set.union(*(d[i] for i in cur)))
        else:
            num = 0
        if num == target:
            ans.add(tuple(sorted(cur)))
            return
        for i in range(start, len(candidates)):
            cur.append(candidates[i])
            dfs(cur, i+1)
            cur.pop()
    dfs([], 0)
    return sorted(ans, key=len)

res = find_cities(list(d.keys()), len(cities))

print (res)

#[('malaga', 'milano', 'paris'), ('barcelona', 'malaga', 'paris'),
# ('barcelona', 'berlin', 'paris'), ('barcelona', 'berlin', 'lisabon'),
# ('berlin', 'milano', 'paris'), ('berlin', 'milano', 'roma'),
# ('barcelona', 'berlin', 'roma'), ('lisabon', 'malaga', 'milano'),
# ('barcelona', 'malaga', 'roma'), ('malaga', 'milano', 'roma'),
# ('barcelona', 'lisabon', 'malaga'), ('berlin', 'lisabon', 'milano'),
# ('barcelona', 'malaga', 'milano', 'paris'), ('berlin', 'malaga', 'milano', 'roma'),
# ('berlin', 'malaga', 'milano', 'paris'), ('barcelona', 'lisabon', 'malaga', 'milano'),
# ('berlin', 'lisabon', 'malaga', 'milano'), ('barcelona', 'berlin', 'lisabon', 'milano'),
# ('barcelona', 'berlin', 'malaga', 'roma'), ('barcelona', 'malaga', 'milano', 'roma'),
# ('barcelona', 'berlin', 'milano', 'roma'), ('barcelona', 'berlin', 'malaga', 'paris'),
# ('barcelona', 'berlin', 'milano', 'paris'), ('barcelona', 'berlin', 'lisabon', 'malaga'),
# ('barcelona', 'berlin', 'malaga', 'milano', 'roma'),
# ('barcelona', 'berlin', 'lisabon', 'malaga', 'milano'),
# ('barcelona', 'berlin', 'malaga', 'milano', 'paris')]

找到列表字典值的最佳组合（可能 pandas）

Find optimal combination of values of a dictionary of lists (perhaps with pandas)

python

dictionary

feature-extraction

dataframe

pandas