从列表中生成具有相同属性的对
Generate pairs having the same attributes from list
假设您有一个项目列表,每个项目都有一组属性。
从具有相同属性的列表中生成所有对的有效算法是什么?
例如,给定一个列表:
[('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})]
我们应该 return 以下列表中的四对,总共有六对:
('item1', 'item2') # both have attribute 'a'
('item1', 'item3') # both have attribute 'b'
('item1', 'item4') # both have attribute 'b'
('item3', 'item4') # both have attribute 'b'
现在,简单的方法是首先生成所有可能的 n(n+1)/2
对的列表,然后过滤掉那些没有相似属性的,但我怀疑这种方法效率低下,特别是如果对的数量很大。
有什么建议吗?
我建议使用两阶段算法:
arr = [('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})]
# 1. create map with for each attribute the list of items that have it
mp = {}
for lst in arr:
for prop in lst[1]:
if prop not in mp: mp[prop] = []
mp[prop].append(lst[0])
# 2. for each attribute: add the pairs of items to the result set
result = set()
for prop in mp:
items = mp[prop]
# collect all pairs in items list
for p1 in range(len(items)):
for p2 in range(p1+1,len(items)):
result.add((items[p1],items[p2]))
print (result)
输出:
{('item1', 'item4'), ('item1', 'item2'), ('item3', 'item4'), ('item1', 'item3')}
假设您有一个项目列表,每个项目都有一组属性。
从具有相同属性的列表中生成所有对的有效算法是什么?
例如,给定一个列表:
[('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})]
我们应该 return 以下列表中的四对,总共有六对:
('item1', 'item2') # both have attribute 'a'
('item1', 'item3') # both have attribute 'b'
('item1', 'item4') # both have attribute 'b'
('item3', 'item4') # both have attribute 'b'
现在,简单的方法是首先生成所有可能的 n(n+1)/2
对的列表,然后过滤掉那些没有相似属性的,但我怀疑这种方法效率低下,特别是如果对的数量很大。
有什么建议吗?
我建议使用两阶段算法:
arr = [('item1', {'a','b'}), ('item2', {'a'}), ('item3', {'c','b'}), ('item4', {'b'})]
# 1. create map with for each attribute the list of items that have it
mp = {}
for lst in arr:
for prop in lst[1]:
if prop not in mp: mp[prop] = []
mp[prop].append(lst[0])
# 2. for each attribute: add the pairs of items to the result set
result = set()
for prop in mp:
items = mp[prop]
# collect all pairs in items list
for p1 in range(len(items)):
for p2 in range(p1+1,len(items)):
result.add((items[p1],items[p2]))
print (result)
输出:
{('item1', 'item4'), ('item1', 'item2'), ('item3', 'item4'), ('item1', 'item3')}