How to find sublist which present one list not another list in python? [duplicate]

Question

This question already has answers here:

Removing duplicates from a list of lists (18 answers)

Python: Remove duplicate lists in list of lists [duplicate] (5 answers)

Closed 6 years ago.

I need to compare two lists which are basically list-of-list find out the sublists which are present in one list but not other. Also the arrangement of the sublists does not consider i.e. ['a','b'] = ['b,'a']. The two lists are

List_1 = [['T_1','T_2'],['T_2','T_3'],['T_1','T_3']]
List_2 = [['T_1','T_2'],['T_3','T_1']]

The output list should be

out_list = [['T_2','T_3']]

• Mateusz Slisz: The answer is already answered. stackoverflow.com/questions/21448310/…
• kederrac: your sublists are unique, like no duplicates in your list?

Answer 1

For two element sublists, this should suffice:

[x for x in List_1 if x not in List_2 and x[::-1] not in List_2]

Code:

List_1 = [['T_1','T_2'],['T_2','T_3'],['T_1','T_3']]
List_2 = [['T_1','T_2'],['T_3','T_1']]
print([x for x in List_1 if x not in List_2 and x[::-1] not in List_2])

• roganjosh: That only reliably works for sublists of 2 items, though
• Austin: @roganjosh, Yes. Already added to my answer. :)
• roganjosh: So I see :) I think we can do better, with set intersection but I'll need to flesh it out a bit in my head. This is going to have to scan the lists twice
• kederrac: is this a 2n^2 solution (time complexity)?

Answer 2

Here's a little messy functional solution that uses sets and tuples in the process (sets are used because what you're trying to calculate is the symmetric difference, and tuples are used because unlike lists, they're hashable, and can be used as set elements):

List_1 = [['T_1','T_2'],['T_2','T_3'],['T_1','T_3']]
List_2 = [['T_1','T_2'],['T_3','T_1']]
f = lambda l : tuple(sorted(l))
out_list = list(map(list, set(map(f, List_1)).symmetric_difference(map(f, List_2))))
print(out_list)

Output:

[['T_2', 'T_3']]

Answer 3

I'd say frozensets are more appropiate for such task:

fs2 = set(map(frozenset,List_2))
out = set(map(frozenset,List_1)).symmetric_difference(fs2)
print(out) 
# {frozenset({'T_2', 'T_3'})}

---

The advantage of using frozensets here is that they can be hashed, hence you can simply map both lists and take the set.symmetric_difference.

---

If you want a nested list from the output, you can simply do:

list(map(list, out))

Note that some sublists might appear in a different order, though given the task should not be a problem

• yatu: Hmm yeah i think ur right @MrGeek
• roganjosh: The issue now is that you don't get a list output, so one way or another, it's gonna look like MrGeek's answer if you follow it through to its entirety
• yatu: Yes, my whole point here is that using sets or frozensets might simply be more appropiate @roganjosh. So not sure what OP wants to do from here, but depending on the task this might be more useful
• yatu: Note that if order is interchangeable as it seems, why not use sets @roganjosh but yeah, if the output has to be a nested lists totally agree
• yatu: Yes yes I know you aren't, just exposing my point of view, agreed :) @roganjosh

Answer 4

You can convert lists to sets for equality comparison and use any() to add into list only items which doesn't exists in second list:

List_1 = [['T_1', 'T_2'], ['T_2', 'T_3'], ['T_1', 'T_3']]
List_2 = [['T_1', 'T_2'], ['T_3', 'T_1']]
out_list = [l1 for l1 in List_1 if not any(set(l1) == set(l2) for l2 in List_2)]

---

For better understanding resources consumption and efficiency of each answer I've done some tests. Hope it'll help to choose best.

Results on data from question:

• Olvin Roght's answer - 12.963876624000001;
• yatu's answer - 8.218290244000002;
• rusu_ro1's answer - 8.857162503000001;
• MrGeek's answer - 11.631234766000002;
• Austin's answer - 3.452045860999995;
• GZ0's answer - 7.037438627.

Results on bigger data:

• Olvin Roght's answer - 83.452110953;
• yatu's answer - 0.1939603360000035;
• rusu_ro1's answer - 0.24479892000000802;
• MrGeek's answer - 0.32636319700000627;
• Austin's answer - 5.052051797000004;
• GZ0's answer - 0.20400504799999908.

• kederrac: what about testing with 1k-10k-1000k, I'm sure that the top will not be the same, with 3 elements the tests are not so relevant
• Olvin Roght: @rusu_ro1, of course. I've added tests with bigger data.
• roganjosh: The timings are interesting but it's not a level playing field. You can see my comments under yatu's answer; it doesn't give back a list.
• roganjosh: Also, Austin's answer flat-out is not extensible. I suspect you have learned something from the timing of your own answer, though :)
• Olvin Roght: @roganjosh, I've updated functions to give back same results. And about my answer - It's not a surprise for me. Actually, it's one of reasons why I've added tests, cause my solution looks most compact but definitely not most efficient ;)

Answer 5

if you do not have duplicates in your lists you can use:

 set(frozenset(e) for e in List_1).symmetric_difference({frozenset(e) for e in List_2})

output:

{frozenset({'T_2', 'T_3'}), frozenset({1, 2})}

if you need a list of lists as output you can use:

[list(o) for o in output]

ouptut:

[['T_2', 'T_3']]

Answer 6

Here is a one-liner variant of the frozenset solutions from @yatu and @rusu_ro1 for those who prefer a more concise syntax:

out = [*map(list,{*map(frozenset,List_1)}^{*map(frozenset,List_2)})]

If it is not required to convert the output into a nested list, just do

out = {*map(frozenset,List_1)}^{*map(frozenset,List_2)}

Meanwhile, one advantage of using the symmetric_difference function rather than the ^ operator is that the former can take any iterable as its argument. This avoids converting map(frozenset,List_2) into a set and therefore gains some performance.

out = [*map(list,{*map(frozenset,List_1)}.symmetric_difference(map(frozenset,List_2)))]