python - 从向量中有效提取边列表的算法

Question

我有一个长列表(约 1000 万个元素)，具有重复值的元素是成对的。我想从列表中提取对列表，例如

R = [1,3,1,6,9,6,1,2,3,0]

将吐出对列表

P = [[e1,e3],[e1,e7],[e3,e7],[e4,e6],[e2,e9]]

对于长列表，实现此目的的有效算法是什么？

Answer 1

根据值将索引组合在一起，然后使用组合遍历成对的索引。

from collections import defaultdict
from itertools import combinations

R = [1,3,1,6,9,6,1,2,3,0]
d = defaultdict(list)
for idx,item in enumerate(R,1):
    d[item].append(idx)

result = []
for indices in d.itervalues():
    result.extend(combinations(indices, 2))

print result

结果:

[(1, 3), (1, 7), (3, 7), (2, 9), (4, 6)]

填充 defaultdict 平均需要 O(len(R)) 时间。寻找组合是 O(N!) 时间，其中 N 是最大组中的索引数。