Найти уникальные элементы в каждом списке среди неизвестного количества списков

Question

Я пытаюсь найти эффективное решение для следующей проблемы:

У меня есть несколько списков x (число неизвестно), каждый из которых имеет разные, но перекрывающиеся элементы. Я хотел бы найти элементы, уникальные для каждого списка, и вывести их отдельно.

Например, если у меня есть 3 списка:

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

Это приведет к выводу (я не пытаюсь найти только уникальные элементы):

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

Предполагается, что один список генерируется последовательно. Я думал об использовании наборов, но считаю, что это можно решить, когда генерируется каждый список.

Answer 1

Вот простое решение в O (N), где N - общее количество элементов.

Основная идея состоит в том, чтобы подсчитать для каждого элемента, сколько раз оно появляется во всех списках. Затем вы можете отфильтровать каждый список, сохранив только элементы, которые появляются один раз.

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))

И вывод:

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

Answer 2

Использовать

• set.difference() - Возвращать набор, содержащий элементы, которые существуют только в наборе x, но не в наборе 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]

Answer 3

Вы можете использовать dict, который хранит количество раз, которое видели каждое число, и использовать его для создания набора, с которым сравниваются списки. С помощью dict это означает, что вам не нужно снова сравнивать каждый новый список со всеми другими списками (но duplicate_numbers необходимо будет переопределить).

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