Finding common items in a list in python
Finding common items in a list in python? Imagine if I have a list like this [[A, b], [a, c], [b, c], [c, d], [e, e], [F, G]] My output should be [A, b, c, d] [E, f, g] How can I do this? What I have tried is like this
for i in range(0,len(fin3)):
for j in range(i+1,len(fin3)):
grop = []
grop = list(set(fin3[i]) & set(fin3[j]))
if len(grop)>0:
grop2 = []
grop2.append(link[i])
grop2.append(link[j])
grop3.append(grop2)
Thanks in advance...
source to share
I think you want something like:
data = [[1, 2], [2, 3], [4, 5]]
output = []
for item1, item2 in data:
for item_set in output:
if item1 in item_set or item2 in item_set:
item_set.update((item1, item2))
break
else:
output.append(set((item1, item2)))
output = map(list, output)
This gives:
output == [[1, 2, 3], [4, 5]]
source to share
If you want to find common elements, even if the lists are not contiguous and if the order in the result doesn't matter:
def condense_sets(sets):
result = []
for candidate in sets:
for current in result:
if candidate & current: # found overlap
current |= candidate # combine (merge sets)
# new items from candidate may create an overlap
# between current set and the remaining result sets
result = condense_sets(result) # merge such sets
break
else: # no common elements found (or result is empty)
result.append(candidate)
return result
Example:
>>> data = [['a','b'], ['a','c'], ['b','c'], ['c','d'], ['e','f'], ['f','g']]
>>> map(list, condense_sets(map(set, data)))
[['a', 'c', 'b', 'd'], ['e', 'g', 'f']]
See Replace a list with a "compressed" list while maintaining order .
source to share
As noted in the comment above, it looks like you want to set up a consolidation.
Here's a solution that I adapted from the code from the link in this comment above.
def consolidate(seq):
if len(seq) < 2:
return seq
result, tail = [seq[0]], consolidate(seq[1:])
for item in tail:
if result[0].intersection(item):
result[0].update(item)
else:
result.append(item)
return result
def main():
sets = [set(pair) for pair in [['a','b'],['a','c'],['b','c'],['c','d'],['e','f'],['f','g']]]
print("Input: {0}".format(sets))
result = consolidate(sets)
print("Result: {0}".format(result))
if __name__ == '__main__':
main()
Output example:
Input: [set(['a', 'b']), set(['a', 'c']), set(['c', 'b']), set(['c', 'd']), set(['e', 'f']), set(['g', 'f'])]
Result: [set(['a', 'c', 'b', 'd']), set(['e', 'g', 'f'])]
source to share
Another approach that looks like (in) effective is O (n ^ 2), where n = number of elements. It's not entirely elegant, but it's correct. The following function returns a set of (hashable) frozensets if you supply a value True
for the named argument return_sets
, otherwise it returns a list of lists (default, since your question indicates what you really want):
def create_equivalence_classes(relation, return_sets=False):
eq_class = {}
for x, y in relation:
# Use tuples of x, y in case either is a string of length > 1 (iterable),
# and so that elements x, y can be noniterables such as ints.
eq_class_x = eq_class.get(x, frozenset( (x,) ))
eq_class_y = eq_class.get(y, frozenset( (y,) ))
join = eq_class_x.union(eq_class_y)
for u in eq_class_x:
eq_class[u] = join
for v in eq_class_y:
eq_class[v] = join
set_of_eq_classes = set(eq_class.values())
if return_sets:
return set_of_eq_classes
else:
return list(map(list, set_of_eq_classes))
Using:
>>> data = [['a','b'], ['a','c'], ['b','c'], ['c','d'], ['e','f'], ['f','g']]
>>> print(create_equivalence_classes(data))
[['d', 'c', 'b', 'a'], ['g', 'f', 'e']]
>>> print(create_equivalence_classes(data, return_sets=False))
{frozenset({'d', 'c', 'b', 'a'}), frozenset({'g', 'f', 'e'})}
>>> data1 = [['aa','bb'], ['bb','cc'], ['bb','dd'], ['fff','ggg'], ['ggg','hhh']]
>>> print(create_equivalence_classes(data1))
[['bb', 'aa', 'dd', 'cc'], ['hhh', 'fff', 'ggg']]
>>> data2 = [[0,1], [2,3], [0,2], [16, 17], [21, 21], [18, 16]]
>>> print(create_equivalence_classes(data2))
[[21], [0, 1, 2, 3], [16, 17, 18]]
source to share