多少公共项目

Question

比方说，我们对这些信息：

UPDATE

Group A - Item 1, Item 2, Item 3 
Group B - Item 1, Item 3 
Group C - Item 3, Item 4 

我想知道哪些组包含最常见的项目：

输出：

Group A - (Item 1 and Item 3) 
Group B - (Item 1 and Item 3) 

你会用什么算法？

Answer 1

所有你所代表的数据集的第一：

data[A] = {1,2,3} 
data[B] = {1,3} 
data[C] = {3,4} 

这是更好地使用数字，所以你可以使用循环，柜台等..所以：

data[0] = {1,2,3} 
data[1] = {1,3} 
data[2] = {3,4} 

然后我会有另一个数据结构，其中包含您有多少匹配的计数器，例如匹配[A] [B] = 2，匹配[A] [C] = 1等等。这是您需要计算的数据结构。如果你这样做，那么你的问题就会减少到在该数据结构中找到最大值。

for i = 0; i < 3; i++ 
    for item in data[i] 
     for j = 0; j < 3; j++ 
     //optimize a little bit (match[A][A] doesn't make sense) 
     if j == i 
      next 
     if item in data[j] 
      matches[i][j]++ 

当然，你可以优化这一些。例如，我们知道匹配[A] [B]将等于[B] [A]，您可以跳过这些迭代。

Answer 2

因此，给定一个组及其包含项目的列表，您希望输出具有相同组的最大数量的组的最大数量的组的标识。

让我们组和项目的列表：

group_items = (
    ('Group A', ('Item 1', 'Item 2', 'Item 3')), 
    ('Group B', ('Item 1', 'Item 3')), 
    ('Group C', ('Item 3', 'Item 4')), 
    ) 

然后让我们存储最大＃项目共享为每个组值，所以我们可以在最后收集所有匹配的群体。我们也会跟踪max的最大值，因为我们可以（而不是返回并重新计算它）。

max_shared = {item[0]:0 for item in group_items} 
num_groups = len(group_items) 
group_sets = {} 
max_max = 0 

现在我们将每组与其他组进行比较，但是我们可以忽略某些比较。正如@Perroloco所提到的，将A组与A组比较没有用，并且计算相交（A，B）与计算相交（B，A）是对称的，所以我们可以从0到N，然后从i + 1到N，而不是做0..N交叉0..N。

我使用的set数据类型，其成本东西构造。所以我缓存了这些集合，因为我们不修改成员资格，只计算交集的成员资格。值得指出的是，尽管交点（A，B）==交点（B，A），但A的MAX与B的MAX的最大值不相同。因此，存在单独的比较为内部最大值和外部最大值。

for i in range(num_groups): 
    outer_name, outer_mem = group_items[i] 

    if outer_name not in group_sets: 
     group_sets[outer_name] = set(outer_mem) 

    outer_set = group_sets[outer_name] 
    outer_max = max_shared[outer_name] 

    for j in range(i+1, num_groups): 
     inner_name, inner_mem = group_items[j] 

     if inner_name not in group_sets: 
      group_sets[inner_name] = set(inner_mem) 

     inner_set = group_sets[inner_name] 

     ni = len(outer_set.intersection(inner_set)) 

     if ni > outer_max: 
      outer_max = max_shared[outer_name] = ni 

     if ni > max_max: 
      max_max = ni 

     if ni > max_shared[inner_name]: 
      max_shared[inner_name] = ni 

print("Overall max # of shared items:", max_max) 

results = [grp for grp,mx in max_shared.items() if mx == max_max] 

print("Groups with that many shared items:", results)