Removing sublists from a list of lists

Question

I'm trying to find the fastest way to solve this problem, say I have a list of lists:

myList = [[1,2,3,4,5],[2,3],[4,5,6,7],[1,2,3],[3,7]]

I'd like to be able to remove all the lists that are sublists of one of the other lists, for example I'd like the following output:

myList = [[1,2,3,4,5],[4,5,6,7],[3,7]]

Where the lists [2,3] and [1,2,3] were removed because they are completely contained in one of the other lists, while [3,7] was not removed because no single list contained all those elements.

I'm not restricted to any one data structure, if a list of lists or a set is easier to work with, that would be fine too.

The best I could come up with was something like this but it doesn't really work because I'm trying to remove from a list while iterating over it. I tried to copy it into a new list but somehow I couldn't get it working right.

for outter in range(0,len(myList)):
outterSet = set(myList[outter])
for inner in range(outter,len(myList)):
    innerSet = set(myList[inner])
    if innerSet.issubset(outterSet):
        myList.remove(innerSet)

Thanks.

Answer 1

The key to solving your problem is a list of sets:

lists = [[1,2,3,4,5],[2,3],[4,5,6,7],[1,2,3],[3,7]]

sets = [set(l) for l in lists]

new_list = [l for l,s in zip(lists, sets) if not any(s < other for other in sets)]

This converts the inner lists to sets, compares each set to every other set to see if it is contained within it (using the < operator) and, if it is not strictly contained within another set, adds the original list to the new list of lists.