将所有具有共同元素的子数组合并为一个子数组

Question

我需要找到所有共享任何共同元素的子数组，并将它们合并成一个子数组。
（我在用Python实现，但任何算法思路都很有帮助）

多维数组的结构如下：

categories = {'car':['automobile','auto'],
             'bike':['vehicle','motorcycle','motorbike','automobile'],
             'software':['computer','macbook','apple','microsoft','mozilla'],
             'firefox':['internet','mozilla','browser']
             'bicycle':['vehicle']}

我想把'car'、'bike'和'bicycle'合并成一个列表（保留第一个列表的键 新列表的键可以是任何相关的键），同时把'software'和'firefox'也合并成一个列表。

性能非常重要。

到目前为止，我能想到的最佳解决方案是维护一个扁平的一维数组，格式是元素 => 列表键（例如 'automobile' => 'car'），然后对多维数组中的每个列表运行以下递归函数（伪代码）：

function merge_similar(list_key):
    For each element in categories[list_key]:
        If flatten_array.has_key(element):
            list_to_merge = flatten_array[element]
            merge_similar(list_to_merge) /* merge other lists which share an element with our newly found similar list */
            categories[list_key] = merge(categories [list_key], categories[list_to_merge])
            delete categories[list_to_merge]

有没有什么办法可以提高它的性能？

谢谢！

Answer 1

在编程的世界里，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。比如，有人可能会在使用某个库时，发现它的功能不太符合自己的需求。这时候，大家就会在网上讨论，寻求解决方案或者替代的方法。

有些人可能会建议使用其他的库，或者提供一些代码示例，帮助解决问题。大家在讨论中分享自己的经验和见解，这样就能让更多的人受益。

总之，编程过程中遇到问题是很正常的，关键是要积极寻求帮助，和其他人交流，找到最适合自己的解决方案。

>>> categories = {'car':['automobile','auto'],
             'bike':['vehicle','motorcycle','motorbike','automobile'],
             'software':['computer','macbook','apple','microsoft','mozilla'],
             'firefox':['internet','mozilla','browser'],
             'bicycle':['vehicle']}
>>> # Use sets for values
>>> for k,v in categories.items(): categories[k] = set(v)

>>> # Acumulate
>>> for k1, v1 in categories.items():
    if v1:
        for k2,v2 in categories.items():
            if v2 and k1 != k2 and v1 & v2:
                v1 |= v2
                categories[k2] = None
        categories[k1] = v1


>>> # Print
>>> for k1, v1 in categories.items():
    if v1: print('%s: %r' %(k1,v1))


bicycle: {'motorbike', 'vehicle', 'auto', 'automobile', 'motorcycle'}
firefox: {'apple', 'mozilla', 'macbook', 'computer', 'internet', 'microsoft', 'browser'}
>>> 

Answer 2

我想象不出递归的解决方案会很快。
使用 list.extend() 会不会太慢了？
你可以这样做：

categories['car'].extend(categories['bike']);
categories['car'].extend(categories['bicycle']);

或者更一般一点，如果你传入一个想要合并的键的列表：

first_key=None;
for key in keys_whose_lists_I_want_to_merge:
    if first_key is None:
        first_key=key;
    else:
        categories[first_key].extend(categories[key]);

如果你要合并很多列表，可以优化这个循环，第一次之后就不再检查 None。可以参考一下 Python 性能技巧 页面上关于“运行时重新映射函数”的提示。

Answer 3

请注意，字典（dict）没有“第一个键”这个概念，因为字典不保持顺序。如果你需要保持某种顺序，就得考虑使用其他的数据结构。

除了顺序的问题，我建议可以从以下内容开始：

def merged(dictoflists):
  result = dict()
  reversed = dict()
  for k, l in dictoflists.iteritems():
    intersecting = set(reversed.get(w) for w in l) - set([None])
    if intersecting:
      pickone = intersecting.pop()
      into = result[pickone]
    else:
      pickone = k
      into = result[k] = set()
    for ok in intersecting:
      into.update(result.pop(ok))
    into.update(l)
    for w in into:
      reversed[w] = pickone
  return dict((k, sorted(l)) for k, l in result.iteritems())

如果顺序对你来说很重要，那么使用 set 就会有问题，你需要更复杂（而且速度更慢）的数据结构。不过，如果是这样的话，你应该先详细说明在各种可能的情况下，你需要遵循哪些具体的顺序要求。