Find unique elements part of each list amongst unknown number of lists

user_6718586 0
Viewed 133

I am trying to find an efficient solution to subsequent problem:

I have a number of x lists (number unknown) with each having different but also overlapping elements. I would like to find the elements unique to each list and output them separately.

For example if I have 3 lists: 

a = [1,2,3,4] 
b = [2,5,6,7]
c = [3,6,8,9]

This would result in an output of (I am not trying to find the unique elements only):

a --> [1,4]
b --> [5,7]
c --> [8,9]

Assuming that one list gets generated sequentially. I was thinking of using sets but believe that this can be solved when each list gets generated.

set list python
3 Answers

Here is a simple solution in O(N) where N is the total number of elements.

The key idea is to count for each elements how many times it appears in all the lists. Then you can filter each list by keeping only elements that appear once.

from collections import Counter

a = [1,2,3,4]
b = [2,5,6,7]
c = [3,6,8,9]

# Count how many times each elements appear.
counter = Counter()

for l in [a,b,c]:
    counter.update(l)

print(counter)

# If an element appears only once, it is an unique element !
for l in [a,b,c]:
    print(*filter(lambda x: counter[x]==1, l))

And the output is:

Counter({2: 2, 3: 2, 6: 2, 1: 1, 4: 1, 5: 1, 7: 1, 8: 1, 9: 1})
1 4
5 7
8 9
user_81180870

Use

  • set.difference() - Return a set that contains the items that only exist in set x, and not in set y:

Ex.

a = [1,2,3,4]
b = [2,5,6,7]
c = [3,6,8,9]

abc = list(set(a).difference(b).difference(c))
bca = list(set(b).difference(c).difference(a))
cab = list(set(c).difference(a).difference(b))

print(abc)
print(bca)
print(cab)

O/P:

[1, 4]
[5, 7]
[8, 9]
user_42865900

You can use a dict that stores the number of times each number is seen and use that to generate a set that lists are compared against. With the dict it means that you don't then need to compare every new list to all other lists again (but duplicate_numbers will need to be redefined).

tracker_dict = dict()
duplicate_numbers = set()
a = [1,2,3,4] 
b = [2,5,6,7]
c = [3,6,8,9]

# Get count of all numbers in all lists
all_lists = [a, b, c]
for l in all_lists:
    for item in l:
        tracker_dict[item] = tracker_dict.get(item, 0) + 1

# Store all duplicate numbers in a set
duplicate_numbers = set([num for num in tracker_dict if tracker_dict[num] > 1])

# Get new lists
new_a = [i for i in a if i not in duplicate_numbers]

# With a new list that is defined afterwards
d = [1, 4, 5, 1]

# Update the tracker_dict and duplicate_numbers set
for item in d:
    tracker_dict[item] = tracker_dict.get(item, 0) + 1
duplicate_numbers = set([num for num in tracker_dict if tracker_dict[num] > 1])

new_d = [i for i in a if i not in duplicate_numbers]
# This does not affect previously processed lists however
user_82282330
Related