Python: Determine if an unsorted list is contained in a 'list of lists', regardless of the order to the elements

Question

I have a similar question to this question: Determine if 2 lists have the same elements, regardless of order?

What is the best/quickest way to determine whether an unsorted list list1 is contained in a 'list of lists' myListOfLists, regardless of the order to the elements in list1? My attempt is wrapped up in the function doSomething(...) which I call many times:

def doSomething(myListOfLists, otherInputs):

    list1 = []
    ...  # do something here with `otherInputs' 
    ...  # which gives `list1' some values

    # now only append `list1' to `myListOfLists' if it doesn't already exist
    # and if it does exist, remove it

    removeFromList = False
    for myList in myListOfLists:
        if sorted(list1) == sorted(myList):
            removeFromList = True
            break

    if removeFromList:
        myListOfLists.remove(list1)
    else:
        myListOfLists.append(list1)

    return myListOfLists

The problem with this is that I need to run the function doSomething(...) approximately 1.0e5 times. As myListOfLists gets bigger with every call of doSomething(...) this becomes massively time consuming.

EDIT:

Some clarification of the task. Let me give an example of the desired output here:

a = []
doSomething(a, [1,2,3])
>> a = [1,2,3]

Because [1,2,3] is not in a, it is appended to a.

doSomething(a, [3,4,5])
>> a = [[1,2,3], [3,4,5]]

Because [3,4,5] is not in a, it is appended to a.

doSomething(a, [1,2,3])
>>[3,4,5]

Because [1,2,3] is in a, it is removed from a.

EDIT:

All lists have the same length.

One optimization at first glance: Don't sort `list1` again every iteration, but instead sort it once before the loop, and store it. — Lukas Graf, Nov 18 '13 at 18:49
What do the contents of the inner lists look like? You may benefit from converting them to tuples / sets temporarily so that they can be more conveniently compared. — g.d.d.c, Nov 18 '13 at 18:49
You didn't say whether a list can contain repeated values (like `[1,3,2,3]` contains more than one `3`). If it can, then attempts based on sets won't always work. — Tim Peters, Nov 18 '13 at 20:08
@TimPeters - all the lists have exactly the same length. I've clarified this now. Thanks! — kd88, Nov 18 '13 at 20:10
Not what I asked ;-) Can a list contained *repeated elements*? The lengths of the lists are irrelevant to that. `[1, 1, 1]` contains `1` three times, for example. And the list `[1, 1, 2]` is the same as the list `[1, 2, 2]` *if* you make each into a set. — Tim Peters, Nov 18 '13 at 20:19
@TimPeters Ah, I see. In principle the lists can contain the repeated elements, but in practice they never will. So I guess the solution I ticked is valid to me but not as a general solution. — kd88, Nov 18 '13 at 20:28
@TimPeters I've now come across an example where I **do** have repeated elements and you're correct the solution based on sets doesn't work. Do you have any tips? I will also post a similar comment under the ticked answer by hcwhsa. Thanks! — kd88, Nov 20 '13 at 13:52

Ashwini Chaudhary · Accepted Answer · 2013-11-18T19:32:10.220

3

You can use sets here:

def doSomething(myListOfLists, otherInputs):
    s = set(otherInputs)           #create set from otherInputs
    for item in myListOfLists: 
        #remove the common items between `s` and current sublist from `s`.
        s -= s.intersection(item) 
        #if `s` is empty, means all items found. Return True
        if not s:                  
            return True
    return not bool(s)
... 
>>> doSomething([[1, 2, 7],[6, 5, 4], [10, 9, 10]], [7, 6, 8])
False
>>> doSomething([[1, 2, 7],[6, 5, 4], [10, 8, 10]], [7, 6, 8])
True

Update 1: Any Sublist contains exactly same items as otherInputs.

def doSomething(myListOfLists, otherInputs):
    s = set(otherInputs)
    return any(set(item) == s for item in myListOfLists)
... 
>>> doSomething([[6, 8, 7],[6, 5, 4], [10, 8, 10]], [7, 6, 8])
True
>>> doSomething([[1, 2, 7],[6, 5, 4], [10, 8, 10]], [7, 6, 8])
False

Update 2: otherInputs is a subset of any of the sublist:

def doSomething(myListOfLists, otherInputs):
    s = set(otherInputs)
    return any(s.issubset(item) for item in myListOfLists)
... 
>>> doSomething([[6, 8, 7],[6, 5, 4], [10, 8, 10]], [7, 6, 8])
True
>>> doSomething([[6, 8, 7, 10],[6, 5, 4], [10, 8, 10]], [7, 6, 8])
True
>>> doSomething([[1, 2, 7],[6, 5, 4], [10, 8, 10]], [7, 6, 8])
False

edited Nov 18 '13 at 19:32

answered Nov 18 '13 at 18:50

Ashwini Chaudhary

244,495
58
464
504

Perhaps I should be more explicit. In this case I would want '[7, 6, 8]' **NOT** to be found in '[[1, 2, 7],[6, 5, 4], [10, 8, 10]]' but **I WOULD** want it to be found in '[[6, 8, 7],[6, 5, 4], [10, 8, 10]]'. I will clarify this in my original post. – kd88 Nov 18 '13 at 19:04
@JoelKlinger Added another solution. – Ashwini Chaudhary Nov 18 '13 at 19:08
@JoelKlinger What if first sublist is `[6, 8, 7, 9]`? – Ashwini Chaudhary Nov 18 '13 at 19:09
Great! **Update 2** is what I need! To anwser your second question, I require the sublists to be identical (other than order of elements) – kd88 Nov 18 '13 at 19:17
as TimPeters commented this solution will not work if there are repeated elements in a list :( Initially this wasn't a problem for me, but now I have found an example in my data where this does occur. Do you an idea how I might work around this? – kd88 Nov 20 '13 at 13:54
1

@JoelKlinger You can use `collections.Counter` then: `c = Counter(otherInputs);return any(Counter(item) == c for item in myListOfLists)`. – Ashwini Chaudhary Nov 20 '13 at 14:01
That's solved it. One point here is I was required to update to python 2.7 to use `Counter`. Thanks! – kd88 Nov 23 '13 at 14:42

score 0 · Answer 2 · answered Nov 18 '13 at 18:50

Use sets

def doSomething(myDictOfLists, otherInputs):

    list1 = []
    ...  # do something here with `otherInputs' 
    ...  # which gives `list1' some values

    # now only append `list1' to `myListOfLists' if it doesn't already exist
    # and if it does exist, remove it
    list1Set = set(list1)
    if list1Set not in myDictOfLists:
        myDictOfLists[list1Set] = list1

    return myDictOfLists

score 0 · Answer 3 · answered Nov 18 '13 at 18:51

0

If you sort given list and then append it to myListOfLists you can use this:

if sorted(list1) in myListOfLists:

answered Nov 18 '13 at 18:51

Farhadix

1,395
2
12
25

score 0 · Answer 4 · answered Nov 18 '13 at 18:54

This algorithm appears to be slightly faster:

l1 = [3, 4, 1, 2, 3]
l2 = [4, 2, 3, 3, 1]
same = True
for i in l1:
    if i not in l2:
        same = False
        break

For 1000000 loops, this takes 1.25399184227 sec on my computer, whilst

same = sorted(l1) == sorted(l2)

takes 1.9238319397 sec.

Python: Determine if an unsorted list is contained in a 'list of lists', regardless of the order to the elements

4 Answers4

Linked

Related