Sequence

I’m learning the CS_61A course since January 2024, but there was a long time I suspended the learning of this course to learn some other subjects like Algorithm and Data Structure, and pwn in CTF.

And now it’s time to continue the learning.

Sequences are a list of Data in a specific order such as queues, arrays and linked lists.

List

We should know that Python does not have a built-in array type (like C arrays) that’s available without importing a module. But there is a list type in Python similar to array in C.

Using of Lists

• Use the index to visit the elements:

  >>> odds = [41, 43, 47, 49]
  >>> odds[0]
  43
  >>> odds[3]
  42
  >>> odds[odds[3] - odds[2]]
  47

• Get the number of elements:

  >>> len(odds)
  4

• Use the getitem function:

  >>> from operator import getitem
  >>> getitem(odds, 3)
  49

• Concatenation and repetition:

  >>> [2, 7] + odds
  [2, 7, 41, 43, 47, 49]
  >>> 2 * odds
  [41, 43, 47, 49, 41, 43, 47, 49]
  >>> from operator import add, mul
  >> add([2, 7], mul(odds, 2))
  [2, 7, 41, 43, 47, 49, 41, 43, 47, 49]

• nested lists

  >>> pairs = [[10, 20], [30, 40]]
  >>> pairs[1]
  [30, 40]
  >>> pairs[1][0]
  30

Containers

In Python, containers are objects that hold other objects, providing a way to organize and manage collections of data.
Some typical containers:

• list
• tuple
• str
• dict
• set

But here what we want to say about is not Container itself, but some using of containers.

>>> digits = [1, 8, 2, 8]
>>> 1 in digits
True
>>> 3 in digits
False

The emphasis is in, an operator between containers and elements. If the element is “in” the container, then this operation returns True, otherwise it’ll return False.

For Statements – the Sequence Iteration

In Python the For statement is a way of iterating over sequences.

Instance

def count(s, value):
  """Count the number of times that a value occurs in sequence s.

  >>> count([1, 2, 3, 1, 2 ,1], 1)
  3
  """

  total = 0
  for element in s:
    if element == value:
      total++
  return total

$ python3 -m doctest -v ex.py
Trying:
    count([1, 2, 3, 1, 2 ,1], 1)
Expecting:
    3
ok
1 items had no tests:
    ex
1 items passed all tests:
    1 tests in ex.count
1 tests in 2 items.
1 passed and 0 failed.
Test passed.

Principle

• How does for statement works?
  1. Evaluate the header expression which must yield an iterable value (a sequence)
  2. For each element in that sequence, in order:
  • a. Bind name to that element in the current frame
  • b. Execute the suit

Extensional Instance

When we process with a sequence of fixed-length sequences, there could be several names of the fixed-length sequences.

• Unpack means reading the containers as several elements in it.

pairs = [[1, 2], [2, 2], [2, 3], [3, 3]]
for x in pairs:
  print(x)

for x, y in pairs:
  print('[x, y] = [', x, ',', y, ']')

$ python ~/Downloads/test.py
[1, 2]
[2, 2]
[2, 3]
[3, 3]
[x, y] = [ 1 , 2 ]
[x, y] = [ 2 , 2 ]
[x, y] = [ 2 , 3 ]
[x, y] = [ 3 , 3 ]

• Notice: the number of name in for statement could only be one or equals to the length of the fixed-length sequences.

Range

A range is a sequence of consecutive integers.*
..., -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5,...

• the length of range: ending value - starting value

>>> range(-2, 2)
range(-2, 2)    # This is a range, not a list, so the output is repetition of your input.
>>> list(range(-2, 2))
[-2, -1, 0, 1]    # Function list() turns the range into a list.
>>> list(range(4))
[0, 1, 2, 3]

Like what you see above, list is a built-in function of Python that turns a sequence into the form of list. So it could turns the range into a list and print it out.

It’s easy to find that:

• a range include it’s first element, but exclude it’s last element.
• if there is only one param for range, the range start from 0, and it’s length would be the param.

Using

With Range types, we could do like this:

def sum_below(n):
  total = 0
  for i in range(n):
    total += i
  return total

$ python -i ex.py
>>> sum_below(5)
10

And this:

def cheer():
  for _ in range(3):    # This element in range is only used to control the rounds of the iteration, so we use '_' to replace it.
    print('Go Bears!')

$ python -i ex.py
>>> cheer()
Go Bears!
Go Bears!
Go Bears!

List Comprehension

A List Comprehension, from my perspective, is just an special expression values to a list.

In Chinese, List Comprehension is usually translated to:

• 列表推导式（最常用）
• 列表解析式
• 列表生成式

The Grammar of List Comprehension

[expression for item in iterable if condition]

• expression: just an expression of item.
• for item in iterable: Iterates over the iterable.
• if condition (optional): Filters items base on a condition.

Example

>>> [x+1 for x in [1, 2, 3]]
[2, 3, 4]
>>> [x for x in [1, 3, 5, 7, 9] if 25 % x == 0]
[1, 5]

Using

With List Comprehension, now we could do like this:

def divisors(n):
  return [1] + [x for x in range(2, n) if n % x == 0]

$ python -i ex.py
>>> divisors(1)
[1]
>>> divisors(12)
[1, 2, 3, 4, 6]

Lists, Slices & Recursion

For any list s, the expression s[1:] is called a slice from index 1 to the end (ro 1 onward).

• The value of s[1:] is a list whose length is one less thant the length of s
• Slicing s doesn’t affect s

Recursion Example

# Compute the sum of elements in a list.
def sum_list(s):
  if len(s) == 0:
    return 0
  else:
    return s[0] + s[1:]

Here is a more complex example, it’s a function which takes a list of positive numbers s and a non-negative number n. It returns the sublist of s with the largest sum that is less than or equal to n.

def large(s, n):
  if s == []:
    return []
  elif s[0] > n:
    return large(s[1:], n)
  else:
    first = s[0]
    with_s0 = [first] + large(s[1:], n - first)
    without_s0 = large(s[1:], n)
    if(sum_list(with_s0) > sum_list(without_s0)):
      return with_s0
    else:
      return without_s0