#!/usr/bin/env python
# coding: utf-8

# # Lists and Other Data Structures 

# ## List Creation and Access

# In[ ]:


L = [10, 20, 30]
L


# In[ ]:


[] # [] is the empty list


# In[ ]:


L[1], len(L), len([])


# In[ ]:


L[2] = 33
L


# In[ ]:


L = [11, 22, 33]
L[-1], L[-2], L[-3]


# In[ ]:


L = [0, 11, 22, 33, 44, 55]


# In[ ]:


L[2:4]


# In[ ]:


L[-4:4]


# In[ ]:


L[2:-2]


# In[ ]:


L[:4]


# In[ ]:


L[4:]


# In[ ]:


L = [0, 11, 22, 33, 44, 55, 66, 77]
L[2:6] = [12, 13, 14]               # substitutes [22, 33, 44, 55]
L


# In[ ]:


L = [0, 11, 22, 33, 44, 55, 66, 77]
L[:1] = []                          # delete the first term of a list
L


# In[ ]:


L = [0, 11, 22, 33, 44, 55, 66, 77]
L[-1:] = []                          # delete the last term of a list
L


# In[ ]:


L = [0, 11, 22, 33, 44, 55, 66, 77]
L[:0] = [100]                          # insert 100 in front of a list
L


# In[ ]:


L = [0, 11, 22, 33, 44, 55, 66, 77]
L[len(L):] = [100]                     # insert 100 in tail of a list
L


# In[ ]:


L = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
L[3:len(L)-5] == L[3-len(L):-5]


# In[ ]:


[5 in L, 6 in L]


# ## Global List Operations

# In[ ]:


L = [1, 2, 3] 
L + [10, 20, 30]


# In[ ]:


4 * [1, 2, 3]


# In[ ]:


L = 5*[10, 20, 30]
L[:3]+L[3:] == L


# In[ ]:


[1..3, 7, 10..13]


# In[ ]:


[1, 4..20, 100, -20..-10]


# In[ ]:


G = map(cos, [0, pi/6, pi/4, pi/3, pi/2])      # generator
L = list(G)                                    # list
L


# In[ ]:


list(G)


# In[ ]:


G = map(lambda t: cos(t), [0, pi/6, pi/4, pi/3, pi/2])
list(G)


# In[ ]:


G = map(lambda t: N(cos(t)), [0, pi/6, pi/4, pi/3, pi/2])
print(list(G))


# In[ ]:


G = map(N, map(cos, [0, pi/6, pi/4, pi/3, pi/2]))
print(list(G))


# In[ ]:


G = map(compose(N, cos), [0, pi/6, pi/4, pi/3, pi/2])
print(list(G))


# In[ ]:


G = filter(is_prime, [1..55])
print(list(G))


# In[ ]:


p = 37
G = filter(lambda n: n^4 % p == 7, [0..p-1])
print(list(G))


# $$\left\{ 2n+1 : n = 0,1,2,\dots, 15 \right\}$$

# In[ ]:


G = map(lambda n: 2*n+1, [0..15])
print(list(G))


# In[ ]:


[2*n+1 for n in [0..15]]   # list comprehension


# $$\left\{ p \in \left\{1,2,\dots, 55\right\} : \text{$p$ is prime.}\right\}$$

# In[ ]:


G = filter(is_prime, [1..55])
print(list(G))


# In[ ]:


[p for p in [1..55] if is_prime(p)]


# $$\left\{ n^2 : n \in \left\{1,2,\dots, 20\right\}  \text{ and $n$ is prime.}\right\}$$

# In[ ]:


G = filter(is_prime, [4*n+1 for n in [0..20]])
print(list(G))


# In[ ]:


[n^2 for n in [1..20] if is_prime(n)]


# In[ ]:


reduce(lambda x, y: 10*x+y, [1, 2, 3, 4])


# In[ ]:


reduce(lambda x, y: x + [[y]], [1, 2, 3, 4], [])


# In[ ]:


L = [2*n+1 for n in [0..9]]
reduce(lambda x, y: x*y, L, 1)


# In[ ]:


prod([2*n+1 for n in [0..9]])    # a list with for


# In[ ]:


prod( 2*n+1 for n in [0..9] )       # without a list


# In[ ]:


prod( n for n in [0..19] if n%2 == 1 )


# In[ ]:


def fct(x):
    return 4/x == 2


# In[ ]:


all(fct(x) for x in [2, 1, 0])


# In[ ]:


any(fct(x) for x in [2, 1, 0])


# In[ ]:


# [fct(x) for x in [2, 1, 0]]   # error


# In[ ]:


[[x, y] for x in [1..2] for y in [6..8]]


# In[ ]:


[ [[x, y] for x in [1..2]] for y in [6..8]]


# In[ ]:


G = map(lambda x, y: [x, y], [1..3], [6..8])
print(list(G))


# In[ ]:


L = [[1, 2, [3]], [4, [5, 6]], [7, [8, [9]]]]


# In[ ]:


flatten(L, max_level = 1)


# In[ ]:


flatten(L, max_level = 2)


# In[ ]:


flatten(L)                 # equivalent to flatten (L, max_level = 3)


# $$(x e^x)^{(n)} = \sum_{k=0}^n \binom{n}{k} x^{(k)} (e^x)^{(n-k)} = (x+n) e^x$$

# In[ ]:


x = var('x')
factor(diff(x*exp(x), [x, x]))


# In[ ]:


G = map(lambda n: factor(diff(x*exp(x), n*[x])), [0..6])
print(list(G))


# In[ ]:


print([factor(diff(x*exp(x), n*[x])) for n in [0..6]])


# ## Main Methods on Lists

# In[ ]:


L = [1, 8, 5, 2, 9]
L.reverse()
L


# In[ ]:


L.sort()
L


# In[ ]:


L.sort(reverse = True)
L


# In[ ]:


L = [1, 8, 5, 2, 9]
L.append(100)
L


# In[ ]:


L = [1, 8, 5, 2, 9]
L.extend([100, 200])
L


# In[ ]:


L = [1, 8, 5, 2, 9]
L.insert(3, 100)
L


# In[ ]:


L = [1, 8, 5, 2, 9, 2, 5, 5]
L.count(5)


# In[ ]:


L = [1, 8, 5, 2, 9, 2, 5, 9, 5]
L.index(9)


# In[ ]:


L = [1, 8, 5, 2, 9, 2, 5, 9, 5]
L.remove(9)
L


# ## Examples of List Manipulations

# In[ ]:


def fct1(L):
    E = list(filter(lambda n: n % 2 == 0, L))
    O = list(filter(lambda n: n % 2 == 1, L))
    return [E, O]
fct1([1..10])


# In[ ]:


def fct2 (L):
    res0 = []
    res1 = []
    for k in L:
        if k%2 == 0: 
            res0.append(k) # or res0[len(res0):] = [k]
        else: 
            res1.append(k) # or res1[len(res1):] = [k]
    return [res0, res1]
fct2([1..10])


# In[ ]:


def fct3a(L, res0, res1):
    if L == []: 
        return [res0, res1]
    elif L[0]%2 == 0: 
        return fct3a(L[1:], res0+[L[0]], res1)
    else: 
        return fct3a(L[1:], res0, res1+[L[0]])
def fct3(L): 
    return fct3a(L, [], [])
fct3([1..10])


# In[ ]:


def subSequences(L):
    if L == []: 
        return []
    res = []
    start = 0
    k = 1
    while k < len(L):         # 2 consecutive terms are defined
        if L[k-1] > L[k]:
            res.append(L[start:k]) 
            start = k
        k = k+1
    res.append(L[start:k])
    return res


# In[ ]:


subSequences([1, 4, 1, 5])


# In[ ]:


subSequences([4, 1, 5, 1])


# ## Character Strings

# In[ ]:


S = 'This is a character string.'
S


# In[ ]:


S = 'This is \n a déjà-vu \t example.'
print(S)
S


# In[ ]:


S = 'one two three four five six seven'
L = S.split()
L


# ## Shared or Duplicated Data Structures

# In[ ]:


L1 = [11, 22, 33]
L2 = L1
L1[1] = 222 
L2.sort() 
L1, L2


# In[ ]:


L1[2:3] = []
L2[0:0] = [6, 7, 8]
L1, L2


# In[ ]:


L1 = [11, 22, 33]
L2 = L1 
L3 = L1[:]
[L1 is L2, L2 is L1, L1 is L3, L1 == L3]


# In[ ]:


La = [1, 2, 3] 
L1 = [1, La] 
L2 = copy(L1)
L1[1][0] = 5           # [1, [5, 2, 3]] for L1 and L2
[L1 == L2, L1 is L2, L1[1] is L2[1]]


# In[ ]:


list(map(copy, L))


# In[ ]:


La = [1, 2, 3]
L1 = [1, La] 
L2 = deepcopy(L1)
L1[1][0] = 5
[L1 == L2, L1 is L2, L1[1] is L2[1]]


# ## Mutable and Immutable Data Structures

# In[ ]:


S0 = ()
S1 = (1, )
S2 = (1, 2)
[1 in S1, 1 == (1)]


# In[ ]:


S1 = (1, 4, 9, 16, 25)
[k for k in S1]


# In[ ]:


L1 = [0..4]
L2 = [5..9]
list(zip(L1, L2))


# In[ ]:


list(map(lambda x, y:(x, y), L1, L2))


# ## Finite Sets

# In[ ]:


E = Set([1, 2, 4, 8, 2, 2, 2])
F = Set([7, 5, 3, 1]) 
E, F


# In[ ]:


E = Set([1, 2, 4, 8, 2, 2, 2])
F = Set([7, 5, 3, 1])
5 in E, 5 in F, E + F == F | E


# In[ ]:


E + F, E | F, E & F, E - F, E ^^ F


# In[ ]:


E = Set([1, 2, 4, 8, 2, 2, 2])
[E[k] for k in [0..len(E)-1]], [t for t in E]


# In[ ]:


def included(E, F): 
    return E+F == F


# In[ ]:


Set([Set([]), Set([1]), Set([2]), Set([1, 2])])


# In[ ]:


Set([ (), (1, ), (2, ), (1, 2) ])


# In[ ]:


def Parts(EE):
    if EE == Set([]): 
        return Set([EE])
    else:
        return withOrWithout(EE[0], Parts(Set(EE[1:])))


# In[ ]:


def withOrWithout(a, E):
    return Set(map (lambda F: Set([a])+F, E)) + E


# In[ ]:


Parts(Set([1, 2, 3]))


# ## Dictionaries

# In[ ]:


D={}
D['one']   = 1
D['two']   = 2
D['three'] = 3
D['ten']   = 10
D['two'] + D['three']


# In[ ]:


D = {'a0':'b0', 'a1':'b1', 'a2':'b2', 'a3':'b0', 'a4':'b3', 'a5':'b3'}
E = Set(D.keys()) ; Imf = Set(D.values())
Imf == Set(map (lambda t: D[t], E)) # is equivalent


# In[ ]:


def injective(D):
    return len(D) == len (Set(D.values()))
injective(D)


# In[ ]:


D = {'a0':'b0', 'a1':'b1', 'a2':'b2', 'a3':'b0', 'a4':'b3', 'a5':'b3'}
F = ['a0', 'a3', 'a4']
G = ['b1', 'b3']


# In[ ]:


Set([D[t] for t in F])              # image f(F)


# In[ ]:


Set([t for t in D if D[t] in G])    # preimage f^{-1}(G)


# In[ ]:


DR = dict((D[t], t) for t in D)     # inverse function of f
DR


# In[ ]: