Programming

  minte9
LearnRemember



Recursion / 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




References