从集合列表中查找项目与多少其他（唯一）元素配对，查找最常配对的元素

Question

我有一个集合列表，我试图从集合中获取与大多数项相关的项–不是最常见的项或发生在大多数集合中的项，而是与大多数项“交互”的项

集合列表示例：

food = [{'avocado', 'banana', 'coffee'}, {'avocado', 'donuts'}, {'coffee', 'licorice'}]

应该返回交互最多的项目，如果有更多的项目具有相同的值，则应该返回按字母顺序排在第一位的项目，在本例中：鳄梨

我已经设法创建了一个dict，其中项目作为键，它们相应的“交互”作为值。按最大值对dict排序（对列表进行排序），最后通过索引所述列表中的第一个元素来获取“交互”最多的项

def goes_with_most(food):
    food_type = {}
    for mixture in food:
        for stuff in mixture:
            if stuff not in food_type:
                food_type[stuff] = len(mixture) - 1     #the number of interactions 
            else: food_type[stuff] += (len(mixture) - 1)
    max_value_ls = sorted(food_type.items(), key=lambda stuff: (-stuff [1], stuff[0]))
    return max_value_ls[0][0]                            #returns the first item with the highest value 

当然，有一个更清洁的解决方案，并将非常感谢提示

Answer 1

您没有非常清楚地指定什么是“交互”。我看到两种可能的解释：

1. 与某物搭配的独特成分的数量。在一个包含{}和{}的列表中，{}与三个独特成分配对：{}、{}和{}
2. 对于每一组，该组中其他成分的数量，无论它们是否存在于其他组中。在一个包含{'advocado', 'coffee', 'banana'}和{'advocado', 'banana', 'chocolate'}的列表中，'advocado'在第一个列表中与两种成分配对，在第二个列表中与两种成分配对，因此有4其他成分与其配对。在这两个集合中都存在'banana'并不重要

您的代码坚持第二种解释，并且您声明代码已经工作。我给你两个的代码

不管怎样，你已经有了正确的想法。您必须执行以下操作：

1. 找到所有独特的元素
2. 找出1中任何项目的其他（唯一）元素数。与…配对

得到1。无法避免对所有输入集以及每个集的所有值进行循环

但是首先：您只需要找到一个获胜的元素，这样您就可以使用max()或min()，并且不需要排序！只有当你需要知道所有食物的准确排名时，分类才有用

为了实现第一种解释，我只需要创建集合的联合，这避免了手动循环和测试包容。您最终得到的集合中，特定成分同时作为键和集合，但由于这适用于所有成分，因此您仍然可以得到正确的答案：

def goes_with_most(food):
    ingredients = {}
    for mixture in food:
        for ingredient in mixture:
            ingredients.setdefault(ingredient, set()).update(mixture)
    return min(ingredients, key=lambda ing: (-len(ingredients[ing]), ing))

请注意这里的排序键：我们不是在寻找最大的，而是使用负集大小，食物名称为领带断路器。对于advocado，返回(-4, 'advocado')，它在(-4, 'coffee')之前排序，因此保持名称按字母顺序排序

您已经使用了这个技巧，但是它需要显式，并且它对min()的作用与对排序的作用一样多

演示：

>>> food = [{'avocado', 'banana', 'coffee'}, {'avocado', 'donuts'}, {'coffee', 'licorice'}]
>>> goes_with_most(food)
'avocado'

第二种解释是您实现的，只需要将集合替换为整数：

def goes_with_most(food):
    counts = {}
    for mixture in food:
        for ingredient in mixture:
            counts[ingredient] = counts.get(ingredient, 0) + len(mixture) - 1
    return min(counts, key=lambda ing: (-counts[ing], ing))

我们可以通过使用^{} instance使其稍微缩短（不需要dict.get(key, 0)）：

from collections import defaultdict

def goes_with_most(food):
    counts = defaultdict(int)
    for mixture in food:
        for ingredient in mixture:
            counts[ingredient] += len(mixture) - 1
    return min(counts, key=lambda ing: (-counts[ing], ing))

Answer 2

如果我正确理解了这个问题，我认为这是一个优雅而简单的方法

第一：有什么食物？我们只需将所有这些“套餐”组合在一起，然后将它们捣碎成一个组合——毕竟，重复的套餐将被删除：

menu = [{'avocado', 'banana', 'coffee'}, {'avocado', 'donuts'}, {'coffee', 'licorice'}]

foods = set.union(*menu)

现在，让我们编写一个函数，找出有多少种食物与给定的食物相容。我们将把食物本身计算在内；这意味着比问题描述中多了一个项目，但对于每个项目，始终多了一个，因此不会影响排序。我们只需抓取包含食物的所有“膳食”，并用它们制作一个子菜单，然后查看它有多少食物：

def compatibility(menu, food):
    meals = [meal for meal in menu if food in meal]
    return len(set.union(*meals))

现在我们可以根据compatibility和名称简单地获得foods的最佳效果。棘手的部分是，我们希望获得最高的兼容性，但在该兼容性级别上是“最低”的字符串。我们不能“否定”字符串，所以我否定兼容性，然后寻找负兼容性的最小值

因此：

min(foods, key=lambda f: (-compatibility(menu, f), f)) # 'avocado'

Answer 3

以下代码应该可以工作：

def goes_with_most(food):
    max_counter = -1
    food_type = {}
    for mixture in food:
        for item in mixture:
            if item not in food_type:
                food_type[item] = 0
            food_type[item] += 1
            max_counter = max(food_type[item], max_counter)
    for item in sorted(food_type.keys()):
        if food_type[item] == max_counter:
            return item

或更短的

def goes_with_most(food):
    items = []
    for f in food:
        items.extend(list(f))
    counter = collections.Counter(items)
    return sorted([i[0] for i in counter.items() if i[1] == max(counter.values())])[0]