# Example:
# * sym-cbal-trees(5,Ts).
# Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
def symmetric_completely_balanced_trees(node_count):
return [tree for tree in completely_balanced_tree(node_count) \
if symmetric_binary_tree(tree)]
# Example:
# * construct([3,2,5,7,1],T).
# T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
# Then use this predicate to test the solution of the problem P56.
# Example:
# * test-symmetric([5,3,18,1,4,12,21]).
# Yes
# * test-symmetric([3,2,5,7,1]).
# No
def construct(nums):
if not nums:
return None
ordered_nums = sorted(nums)
center_index = (len(nums) / 2)
return (ordered_nums[center_index], construct(ordered_nums[:center_index]), construct(ordered_nums[center_index+1:]))
def test_symmetric(nums):
return symmetric_binary_tree(construct(nums))
# Example in Haskell:
# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
# False
# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
# True
def mirror(tree):
if tree == None:
return None
else:
val, left, right = tree
return (None, mirror(right), mirror(left))
def symmetric_binary_tree(tree):
return mirror(mirror(tree)) == mirror(tree)
# Example:
# * cbal-tree(4,T).
# T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
# T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
# etc......No
def completely_balanced_trees(node_count):
if node_count == 0:
return [None]
else:
right_count = (node_count - 1) / 2
left_count = (node_count - 1) - right_count
left_trees = completely_balanced_trees(left_count)
right_trees = completely_balanced_trees(right_count)
trees = []
for left in left_trees:
for right in right_trees:
trees.append(("x", left, right))
if left_count != right_count:
trees.append(("x", right, left))
return trees
* (istree (a (b nil nil) nil))
T
* (istree (a (b nil nil)))
NIL
def is_tree(t):
if t == None:
return True
elif type(t) == tuple and len(t) == 3:
(val, left, right) = t
return is_tree(left) and is_tree(right)
return False
# stats: [(letter, count)]
# return: [(count, letter OR (left, right)]
def make_tree(stats):
pool = sorted([(count, letter) for letter, count in stats])
while len(pool) > 1:
first = pool.pop(0)
second = pool.pop(0)
node = (first[0]+second[0], (first, second))
pool.append(node)
pool.sort()
return pool[0]
def codes_from_tree(node, path, results):
count, letter_or_trees = node
letter = left = right = None
if type(letter_or_trees) == tuple:
left, right = letter_or_trees
else:
letter = letter_or_trees
if letter:
results.append((letter, path))
else:
codes_from_tree(left, path+"0", results)
codes_from_tree(right, path+"1", results)
def huffman(stats):
results = []
tree = make_tree(stats)
codes_from_tree(tree, "", results)
#to sort by huffman code value
#results.sort(key=lambda x: int(x[1], 2))
results.sort()
return results
n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010',´110´,´111´,´101´,´100´].
def gray(n):
if n == 0:
yield ""
else:
base = list(gray_code(n-1))
for code in base:
yield "0"+code
for code in reversed(base):
yield "1"+code
Example:
* (table (A,B,C) (A and (B or C) equ A and B or A and C))
true true true true
true true fail true
true fail true true
true fail fail true
fail true true true
fail true fail true
fail fail true true
fail fail fail true
def int_to_bool_tuple(x,size):
result = []
while x:
result.insert(0, (x & 1) == 1)
x >>= 1
return ([False]*(size-len(result))) + result
def table2(var_count, func):
for x in range(2**var_count):
bools = int_to_bool_tuple(x,var_count)
for b in bools:
print "%-5s" % b,
print func(*bools)
def and_(x,y): return x and y
def or_ (x,y): return x or y
def not_(x): return not x
def nand_(x,y): return not (x and y)
def nor_(x,y): return not (x or y)
def xor_(x,y): return x ^ y
def impl_(x,y):return not x or y
def equ_(x,y): return x == y
def bool_table(func):
inputs = [(x,y) for x in (True,False) for y in (True,False)]
for x,y in inputs:
print "%-5s %-5s %-5s" % (x,y,func(x,y))
# using goldbach as defined previously
def goldbach_list(start,end,threshold=None):
start = max([start,4])
for n in range(start,end+1):
if n % 2 == 0:
i,j = goldbach(n)
if threshold == None or i > threshold:
print "%d = %d + %d" % (n, i, j)
# using primes_range from previous problem
def goldbach(n):
assert n % 2 == 0
for i in primes_range(2, n):
for j in primes_range(i, n):
if i + j == n:
return (i,j)
# using is_prime from earlier problem
def primes_range(start,end):
return [n for n in range(start, end+1) if is_prime(n)]
# using prime_factors_mult from earlier
def totient_phi2(n):
if n == 1:
return 1
def product(lst):
return reduce(lambda x,y: x*y, lst)
return product([((p-1)*(p**(m-1))) for (p, m) in prime_factors_mult(n)])
#using prime_factors from the previous problem
import itertools
def prime_factors_mult(n):
return [(x, len(list(y))) for x,y in itertools.groupby(prime_factors(n))]
def prime_factors(n):
factor = 2
while n > 1:
if n % factor == 0:
yield factor
n = n / factor
else:
factor += 1
# using coprime defined previously
def totient_phi(m):
if m == 1:
return 1
return len([r for r in range(1,m) if coprime(r,m)])
def coprime(m,n):
return gcd(m,n) == 1
def gcd(m,n):
m,n = sorted([m,n])
while m != 0:
m, n = (n % m), m
return n
import math
def is_prime(n):
for test in range(2, int(math.sqrt(n) + 1)):
if n % test == 0:
return False
return True
primes = sieve [2..]
where sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0]
sorted(lst_of_lsts, key=lambda x: len(x))
sorted(sorted(lst_of_lsts), key=lambda x: len(x))
def length_frequency_sort(lst_of_lists):
freqs = {}
for lst in lst_of_lists:
freqs.setdefault(len(lst), 0)
freqs[len(lst)] += 1
return sorted(lst_of_lists, key=lambda x: freqs[len(x)])
