3

In this question there is a good answer on how to check if a list is contained in another list.

However how can I check if a list is contained in another list but taking into account the order?

For example

a= [1,2,3,5]
b= [1,2,3,4,5]

if set(a).issubset(b):
    print('a is contained in b')
else:
    print('No')

gives me obviously "a is contained in b" Unfortunately if a= [1,3,2,5] it gives me the same result

I would like the following

  • a=[1,3,2,5] -> No
  • a=[1,2,3,5] -> Yes
  • a=[3,4,5] -> yes
  • a=[1,2,4,3,5] -> No
  • a=[1,2,3,4,5] -> Yes
KansaiRobot
  • 7,564
  • 11
  • 71
  • 150
  • 5
    As a general algorithm: iterate both lists in parallel, if the current item in `a` is the same as `b`, advance both iterators, if they're different, only advance `b`'s iterator. If you exhaust `a`'s iterator this way, `a` is a subset of `b`. If you reach `b`'s end first, it is not. – deceze Sep 14 '21 at 10:11
  • 1
    does it include the order ? for example list b be [1,1,2,3,3,4,6,6,5]. then in this case a in b ? – sahasrara62 Sep 14 '21 at 10:11
  • @deceze Thanks. I was planning to do that but since python has usually a different way to do things, I was wondering if no iteration is possible – KansaiRobot Sep 14 '21 at 10:12
  • @sahasrara62 I tried `a in b` with `a=[1,2,3,5]`. It failed – KansaiRobot Sep 14 '21 at 10:14
  • You'll have to iterate one way or another, even if that can be dressed up and hidden some way or another… But sure, off the top of my head I couldn't think of builtins that would give you this behaviour "for free", but maybe someone can come up with something. – deceze Sep 14 '21 at 10:15
  • if that would be only about the exact consecutive sequence, I could think of one trick, but if the result should be `True` for `[1,2,3,5]` where `4` is omited, then I dont think there's an easy way. You have to do the iterations + comparisons. – yedpodtrzitko Sep 14 '21 at 10:17
  • so order matters and all enement in a should be in b in consecutive manner ? it seem to be a competative programming problem, it would be great if you share the link – sahasrara62 Sep 14 '21 at 10:18
  • @sahasrara62 yes – KansaiRobot Sep 14 '21 at 10:19
  • 1
    Possible duplicate of [this question](https://stackoverflow.com/q/29954748/1639625)? – tobias_k Sep 14 '21 at 10:21
  • Does this answer your question? [How to test if one string is a subsequence of another?](https://stackoverflow.com/questions/24017363/how-to-test-if-one-string-is-a-subsequence-of-another) – no comment Sep 14 '21 at 10:23
  • 1
    @KansaiRobot share challenge link ? – sahasrara62 Sep 14 '21 at 10:28
  • string solutions for lists? mmmmmm – KansaiRobot Sep 14 '21 at 11:23
  • 2
    @KansaiRobot Generic Iterable solutions for iterables. – tobias_k Sep 14 '21 at 11:25

2 Answers2

0

Try it:

def IsInList(a:list, b:list):
    for c in a:
        if c in b:
            b = b[b.index(c):]
        else:
            return False
    return True

I tried it:

print(IsInList([1, 3, 2, 5], b))
print(IsInList([1, 2, 3, 5], b))
print(IsInList([3, 4, 5], b))
print(IsInList([1, 2, 4, 3, 5], b))
print(IsInList([1, 2, 3, 4, 5], b))

Output:

False
True
True
False
True

I hope it was useful Nohab

Nohab
  • 39
  • 6
0

It's a bit lengthy, but pretty straight forward: try to iterate both lists in parallel and compare each item to each other. If they're the same, move on to the next item for both lists. If they're different, only move on b's iterator, expecting that there's an additional item in b. If you ever reach a's end this way, it is a subset of b. If you reach b's end first, it wasn't.

def is_subset_in_order(a, b):
    ia, ib = iter(a), iter(b)
    va, vb = next(ia), next(ib)
    
    while True:
        if va == vb:
            try:
                va = next(ia)
            except StopIteration:
                return True
    
        try:
            vb = next(ib)
        except StopIteration:
            return False

b = [1, 2, 3, 4, 5]
assert is_subset_in_order([1, 2, 3, 5], b)
assert not is_subset_in_order([1, 3, 2, 5], b)
assert is_subset_in_order([3, 4, 5], b)
assert not is_subset_in_order([1, 2, 4, 3, 5], b)
assert is_subset_in_order([1, 2, 3, 4, 5], b)
assert is_subset_in_order([1, 1, 2, 2, 3, 3, 1, 1], [1, 1, 2, 5, 2, 3, 42, 3, 1, 1, 6])
deceze
  • 510,633
  • 85
  • 743
  • 889
  • 1
    That doesn't work with empty lists. – no comment Sep 14 '21 at 10:50
  • And "subset" sounds inappropriate if you allow duplicate values. – no comment Sep 14 '21 at 10:51
  • I'll leave that up to OP whether it should be in error when either list is empty. There's precedent for that, e.g. `max`. And yeah, okay, you may want to name this something else. – deceze Sep 14 '21 at 10:57
  • `max` is different, as an empty collection simply doesn't have a maximum. But for subsequence, empty is not a problem. – no comment Sep 14 '21 at 11:03
  • You can argue that either way; is an empty sequence contained within another sequence, or must at least one element actually be contained. That's business rules for OP to decide. – deceze Sep 14 '21 at 11:04
  • I hope they don't decide against all of math and compsci like you did :-P – no comment Sep 14 '21 at 11:04