Remove an item from a list contained in another item in python

[supuflounder]

What about [4,3], [2,5], [6,4]. [4,2,5]?

It is looking like O(n^2); it may be worse. Knowing the actual rejection criteria is important, because that determines the complexity. It is not possible to infer the desired result from the examples given.

Well yes you can because i said i want to remove items that are completly contain in another item, which means [4,3] and [2,5] is contained in [2,3,4,5]. [6,4] is an item you invented which would be removed , because it is contained in [4,5,6] and [2,4,5] would be removed because it is contained in [2,3,4,5]. And in my example the item [4,5,6] is not completely contained in a previous item of "l" because the 6 is not an element of [2,3,4,5]. And I don't understand what you mean by O(n^2). You have to think about it like Venn diagrams. If an an ensemble is within a bigger ensemble, remove the ensemble within. Imagine another list c = ["Cat", "Catnip"] remove 'Cat' because it is contained in "Catnip" so the result would be c = ["Catnip"]

But removing "Cat" when "Catnip" is present is not the same as removing "tin", because "tin" is fully contained in "catnip".

The naïve algorithm works like this:

Take the first element of the list. This is the "current element"

Now, for each remaining element ("selected element") of the list, extract each value, and ask if the value is in the current element. If, for all values in the selected element, they are in the current element, eliminate the selected element.

This could be done by taking each value in the selected element, and if it appears in the current element, remove it from the (copy of) the selected element. If, at the end of the elements of the selected element, the (copy of) the selected element list is empty, then remove the selected element from the main list.

Now, take an element from the remaining list, call it the current element, and repeat for all other elements from the list. You have to deal with the fact that removing the selected element from the list changes your indexing. So, essentially, each time you remove an element from the list, you have to start at the beginning. There are some optimizations that are possible, but this begins to look like O(n^2) for the basic comparisons, and then O(n) for having to start over at the beginning each time, so I get O(n^3) where n is the total number of values contained in the list.

It ain't pretty, or fast, but it works. Depending on the sizes of your lists, this may run in acceptable time bounds.

Key here is to write out the algorithm in terms of little boxes with pieces of paper in them with numbers written on the pieces of paper. Or letters. It doesn't matter. Explain to a first-grader how to eliminate any box whose values are all contained in another box. Tell them that they cannot just lay out all the pieces of paper, but have to reach in, extract a piece of paper, then, one at a time, pull from the "current box" in front of them each value, in turn. If the values match, throw away the paper from the selected box; if they don't match, put the paper down in front of the selected box. If, at the end, the selected box has no pieces of paper left in front of it, throw the box away. Write this out so a reasonably literate first-grader can read it. Once you have this debugged (easier if you have access to a first-grader), just translate it into Python.

If you can write that down, you can program it in Python, because that is just syntax.