- ALGORITHMS //
- RECURSION //
- Call Stack
- Iterative Approach
- Memoization
-
Head Tail
Click to Flip Card
Head Tail
What is the head-tail technique?
How do we reverse a string?
What is a permutation of a set {A,B,C}?
How can we find the permutations of a set?
Reverse string
To reverse a string we place the head behind the tail.
""" Reverse strings / Head tail technique
A classic recursive algorithm, even though the iterative solution is better.
"""
def reverse_string_recursive(str):
if len(str) <= 1: # Base case
return str
head = str[0]
tail = str[1:]
res = reverse_string_recursive(tail) + head
return res
def reverse_string_iterative(str):
m = len(str)
s = ""
for i in range(1, m + 1):
s += str[m - i]
return s
assert reverse_string_recursive('S') == 'S'
assert reverse_string_recursive('XY') == 'YX'
assert reverse_string_recursive('CAT') == 'TAC'
assert reverse_string_recursive('Hello World!') == '!dlroW olleH'
assert reverse_string_iterative('S') == 'S'
assert reverse_string_iterative('XY') == 'YX'
assert reverse_string_iterative('CAT') == 'TAC'
assert reverse_string_iterative('Hello World!') == '!dlroW olleH'
# Overflow
try:
reverse_string_recursive('a' * 1000)
except RecursionError as e:
print(e) # maximum recursion depth exceeded
str = reverse_string_iterative('a' * 1000)
print(str)
Palindrome
A palindrome is a word spelled the same forward or backward.
""" Palindrome / Head tail technique
A palindrome is a word or phrase that is spelled the same
when written forward or backword (level, rotor, civic, race car).
The iterative technique is better!
"""
def isPalindrome_recursive(s):
if len(s) <= 1: # Base case
return True
first = s[0]
last = s[-1]
middle = s[1:-1]
if first == last:
return isPalindrome_recursive(middle) # Recursive
return False
def isPalindrome_iterative(s):
m = len(s)
for i in range(0, m):
first = s[i]
last = s[m-1-i]
if first != last:
return False
return True
# Tests
assert isPalindrome_recursive('level') == True
assert isPalindrome_recursive('rac e car') == True
assert isPalindrome_recursive('levels') == False
assert isPalindrome_recursive('race car') == False
assert isPalindrome_iterative('level') == True
assert isPalindrome_iterative('rac e car') == True
assert isPalindrome_iterative('levels') == False
assert isPalindrome_iterative('race car') == False
# Overflow
import random
def generate_palindrome(length):
# Random integer between 97 and 122 (inclusive), which are
# ASCII codes for the lowercase letters a to z
chars = [chr(random.randint(97, 122)) for _ in range(length//2)]
# Reversed copy of the chars list
reversed = chars[::-1]
return ''.join(chars + reversed)
str_random = generate_palindrome(2000)
print(str_random)
try:
print(isPalindrome_recursive(str_random))
except RecursionError as e:
print("isPalindorme_recursive(str2000)", e)
print("isPalindrome_iterative(str2000)", isPalindrome_iterative(str_random))
"""
isPalindorme_recursive(str2000) maximum recursion depth exceeded ...
isPalindrome_iterative(str2000) True
"""
Head Permutations
A permutation is a specific ordering of all elements of a set.
""" Head Permutations
A set is a collection of unique objects {A,B,C}.
Order doesn't matter for a set, {A,B,C} is the same as {B,A,C}
A set like {A,B,C,A} has repeate A and so is not a set.
Head permutations, we place the head in every posible location of the tail.
The permutation of a single char is the char itself (base case).
By putting the B in every possible location of C we get BC CB.
BC = None + B + C # tail[0:0] = None
CB = C + B + None # tail[1:] = None
"""
def head_permutations(chars):
head = chars[0] # B
tail = chars[1:] # C
prms = []
for k in range(len(tail) + 1):
prms.append(tail[0:k] + head + tail[k:])
return prms
print(', '.join(head_permutations('BC'))) # BC, CB
print(', '.join(head_permutations('BCD'))) # BCD, CBD, CDB
Permutations
A permutation of a set is a specific ordering of all elements.
""" Permutations / Without repetition
A permutation of a set is a specific ordering of all elements.
For example {A,B,C} has six permutations ABC ACB BAC BCA CAB CBA
We select one of the elements from the set as the head.
We get all the permutations from the rest of elements (the tail).
For each permutation we place the head in every posible location.
The permutation of a single char is the char itself (base case).
By putting the B in every possible location of C we get BC CB.
"""
def get_permutations(chars):
if len(chars) == 1:
return [chars] # C
head = chars[0] # A
tail = chars[1:] # BC
tail_prms = get_permutations(tail) # C / BC CB
prms = []
for tail in tail_prms:
for k in range(len(tail) + 1):
prms.append(tail[0:k] + head + tail[k:])
return prms # BC CB
print("Permutations without repetition:")
P1 = get_permutations('ABC')
P2 = get_permutations('ABCD')
print(len(P1), ' '.join(P1)) # 6 ABC BAC BCA ACB CAB CBA
print(len(P2), ' '.join(P2)) # 24 24 ABCD BACD BCAD BCDA ACBD ...
Combinations
A combination is a selection of elements from a set, and order doesn't matter.
""" K-Combinations
Generating all k-combinations of a set is a bit tricky.
You don't want your algorithm to generatate duplicates.
For AB 2-combination from a set {A,B,C} you don't want also create BA,
because is the same 2-combination as AB
When k=0 we need to return a list containing a single empty string.
Otherwise the C1 will return an empty list.
When s='' we return an empty list so that both C1 and C2 recursive cases
will return an empty list.
"""
def combinations(s, k):
if k == 0: return [''] # Base case
if s == '': return [] # Base case
head = s[:1]
tail = s[1:]
# Combintations that include the head
C1 = [head + c for c in combinations(tail, k-1)]
# Combinations without the head
C2 = combinations(tail, k)
return C1 + C2
print("K-Combinations:")
print(' '.join(combinations('ABC', 2))) # AB AC BC
print(' '.join(combinations('ABCD', 3))) # ABC ABD ACD BCD
Last update: 203 days ago
