Блог

Следующая проблема скорее связана с алгоритмом, чем с проблемой кода.

Представьте, что у меня есть структура данных следующим образом:

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

Есть куча характеристик, которые можно найти в разных городах.
Каково минимальное количество городов, которое охватывает все эти характеристики. Т.Е. минимальное количество городов, которые я должен посетить, чтобы получить все преимущества.

До сих пор я начал использовать счетчик

 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’] предполагая, что эта комбинация охватывает все характеристики.

Один из способов продвижения вперед — создать все комбинации (используя 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
  

На самом деле это похоже на задачу о сумме комбинаций, но вместо целевой суммы вам нужна длина объединения множеств.

Сначала измените свой 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')]