Hadron DaVinci

Find Contiguous Sub-Sequence

01 Jan 2021 - Hadron DaVinci

For many programming challenges, it is often beneficial to find contiguous sub-sequences
given a sequence. Note, the sequence may represent an array, a string, etc.

Problem

Given an array, find contiguous subarrays.

Example

given A = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’]
foo(A)

produces the following:

['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'c', 'd', 'e']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'c', 'd', 'e']
['c']
['c', 'd']
['c', 'd', 'e']
['d']
['d', 'e']
['e']

Methods

Method 1

• Time Complexity: O(N^2)
  
  • total Time Complexity is N * N/2 = O(N^2)
    
  • Outer loop of generator will have Time Complexity of N
  • Inner loop of generator will have Time Complexity of N/2
    • Every inner loop reduces size of elements by 1
      which reduces the overall number of inner loop steps by half.
      See example:
    • Example given sequence [1,2,3,4]:
      • elements analyzed not reducing size each time:
        • 1, 2, 3, 4
        • 1, 2, 3, 4
        • 1, 2, 3, 4
        • 1, 2, 3, 4
      • elements analyzed reducing size by 1 each time:
        • 1, 2, 3, 4
        • 1, 2, 3
        • 1, 2,
        • 1
• Spatial Complexity: O(N)
  • max spatial complexity is N
  • min spatial complexity is 1
    
    

Method 1 Summary
Yield all elements between a moving left wall and a moving right wall.

1. In outer loop, Determine left_wall by looping through each index
   • call left_wall lw
2. In inner loop, Determine right_wall by looping through indices lw to the last index
   • call right_wall rw
3. Yield sequence sequence[lw: rw +1]
   • Note we use rw + 1 to compensate for the fact that the
     sequence[x: y] in Python means [x, y) in interval notation.
     
   • Specifically, the interval created by sequence[x: y] includes x, and ends right before y

Method 1 Solution

from typing import Generator

def sub_seq(s: list) -> Generator:
    """
    Returns sub contiguous sequences in s
    :param s: some sequence
    :return:
    """
    for lw in range(0, len(s)):
        for rw in range(lw, len(s)):
            yield s[lw: rw + 1]     # s[lw, rw] in interval notation

# Try Code
if __name__ == "__main__":
    for s in sub_seq(['a', 'b', 'c', 'd', 'e']):
        print(s)

Files

method1.py