HatchLib
Hatch Alpha algorithm library
Contents
-
dynamic programming
-
hatchlib.dynamic.lcs(str1,str2)
longest common sequence
returns the longest sequence contained in both strings
lcs('doom','poof')
returns'oo'
-
-
encoding
-
hatchlib.encoding.huffman(s)
huffman coding
returns the huffman-encoded dictionary ofs
huffman('test')
returns{'e': '00','s': '01','t': '1'}
-
-
factorization
-
hatchlib.factorize.fermat(n)
fermat algorithm
returns the prime factors of a number
fermat(15)
returns[3,5]
-
hatchlib.factorize.pollard_rho(x)
Pollard's rho algorithm
returns the prime factors of a number
pollard_rho(10)
returns[2,5]
-
hatchlib.factorize.trial_div(n)
trial division
return naively derived prime factors
trial_div(20)
returns[2,5]
-
-
math
-
hatchlib.math.lcm(a,b)
lowest common multiple
return the lowest multiple shared bya
andb
lcm(12,15)
returns3
-
hatchlib.math.euclid(a,b)
euclidian algorithm
returns gcd ofa
andb
euclid(12,16)
returns4
-
hatchlib.math.coprime(*n)
unlimited argument coprime check
checks if all arguments are coprime
coprime(5,11,21)
returnsTrue
hatchlib.math.isprime(n)
check if a number is prime
isprime(17)
returnsTrue
-
sequence
-
hatchlib.math.sequence.hailstone(n)
hailstone sequence
returns a hailstone sequence beginning at n
hailstone(13)
returns[13,40,20,10,5,16,8,4,2,1]
-
hatchlib.math.sequence.nth_fib(n)
nth fibonacci number
returns the nth number of the fibonacci sequence
nth_fib(11)
returns89
-
hatchlib.math.sequence.fibonacci(n)
fibonacci sequence
generate n terms of the fibonacci sequencefibonacci(10)
returns[1,1,2,3,5,8,13,21,34,55,89]
-
-
sieve
-
hatchlib.math.sieve.erat(lim)
Eratosthenes' sieve
generate primes with Eratosthenes' sieve up tolim
erat(30)
returns[2,3,5,7,11,13,17,19,23,29]
-
hatchlib.math.sieve.atkin(lim)
Atkin's sieve
generate primes with Atkin's sieve up tolim
atkin(30)
returns[2,3,5,7,11,13,17,19,23,29]
-
-
-
search
-
hatchlib.search.binary
binary search
return0
or1
ifkey
is found in either position, else returnFalse
binary([1,2,3,4],3)
returnsFalse
-
hatchlib.search.kmp(s,sub)
kmp search
return indicies ofsub
ins
kmp('test123','123')
returns[4]
-
hatchlib.search.rabin_karp(s,sub)
Rabin-Karp search
returns indicies ofsub
ins
rabin_karp('test1231','1')
returns[4,7]
-
-
shuffle
-
hatchlib.shuffle.knuth(seq)
knuth algorithm
shufflesseq
knuth([1,2,3,4,5])
retruns[1, 2, 5, 3, 4]
, as an example
-
-
sort
-
hatchlib.sort.cocktail(seq)
cocktail sort
sortsseq
in ascending order
cocktail([2,4,1,6,3,5])
returns[1,2,3,4,5,6]
-
hatchlib.sort.gnome(seq)
gnome sort
sortsseq
in ascending order
gnome([3,5,2,6,1,4])
returns[1,2,3,4,5,6]
-
hatchlib.sort.insertion(seq)
insertion sort sortsseq
in ascending order
insertion([3,5,2,1,4,6])
returns[1,2,3,4,5,6]
-
hatchlib.sort.quicksort(seq)
quicksort algorithm
sortsseq
in ascending order
quicksort([3, 6, 1, 5, 2, 4])
returns[1,2,3,4,5,6]
-
hatchlib.sort.selection(seq)
selection sort
sortsseq
in ascending order
selection([4,3,6,1,2,5])
returns[1,2,3,4,5,6]
-
Notes to students
Install with the following command in c9 terminal:
sudo pip install hatchlib
and update with:
sudo pip install -U hatchlib