Home > documentation, number theory, programming, Python, Sage > List within a list

List within a list

The problem below was asked on the AskSage forum. Below I restate the problem and three possible solutions.

Problem

I have a short list of primes

sage: L = [2, 5, 23]

and a longer list of primes

sage: P = primes_first_n(20); P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

How do I check that all members of L are contained within P?

Solution

You can use a brute-force search by defining your own custom function. This option doesn’t assume that elements in your lists are unique. Your lists can contain duplicate elements if you want.

sage: def is_sublist(shortlist, longlist):
....:     for e in shortlist:
....:         if not (e in longlist):
....:             return False
....:     return True
....: 
sage: L = [2, 5, 23]
sage: P = primes_first_n(20); P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
sage: is_sublist(L, P)
True
sage: L + [23]
[2, 5, 23, 23]
sage: is_sublist(L + [23], P)
True
sage: L.append(next_prime(P[-1])); L
[2, 5, 23, 73]
sage: is_sublist(L, P)
False
sage: is_sublist(L + [23], P)
False

Alternatively, you can use the built-in functions itertools.imap and all. The function itertools.imap is efficient when your lists are large, e.g. having hundreds or even hundreds of thousands of elements. This second option doesn’t care if your lists have duplicate elements.

sage: import itertools
sage: L = [2, 5, 23]
sage: P = primes_first_n(20); P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
sage: L + [23]
[2, 5, 23, 23]
sage: all(itertools.imap(lambda x: x in P, L))
True
sage: all(itertools.imap(lambda x: x in P, L + [23]))
True
sage: L.append(next_prime(P[-1])); L
[2, 5, 23, 73]
sage: all(itertools.imap(lambda x: x in P, L))
False
sage: all(itertools.imap(lambda x: x in P, L + [23]))
False

Or, as Mitesh Patel said, you could use set. This third approach assumes that the elements in each list are unique, i.e. each list doesn’t contain duplicate elements.

sage: L = [2, 5, 23]
sage: P = set(primes_first_n(20))
sage: set(L)
set([2, 5, 23])
sage: set(L).issubset(P)
True
sage: set(L + [23])
set([2, 5, 23])
sage: set(L + [23]).issubset(P)
True
sage: L.append(111); L
[2, 5, 23, 111]
sage: set(L)
set([2, 111, 5, 23])
sage: set(L + [111])
set([2, 111, 5, 23])
sage: set(L + [111]).issubset(P)
False
sage: set(L).issubset(P)
False
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: