# minte9 LearnRemember

### 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
tail = str[1:]
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
"""
``````

A permutation is a specific ordering of all elements of a set.
``````

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
"""

tail = chars[1:] # C
prms = []
for k in range(len(tail) + 1):

return prms

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

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):

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

tail = s[1:]

# Combintations that include the head
C1 = [head + c for c in combinations(tail, k-1)]