Repository files navigation

Library of Algorithms, Data Structures, variety of solutions to common CS problems.

Add this line to your application as managed dependency:

py-algorithms>=0,<1

Or install it globally/locally usingpip package manager:

$ pip install py-algorithms

  - Deque  - Stack (LIFO)  - Queue (FIFO)  - Fibonacci Heap (https://en.wikipedia.org/wiki/Fibonacci_heap)    - Min Heap    - Max Heap  - Priority Queue (Fibonacci)    - Min PQ    - Max PQ  - Suffix Array

  - Binary Search

  - Quick Sort  - Shell Sort (Shell method)  - Heap Sort (Fibonacci heap)  - Merge Sort  - Comb Sort  - Bubble Sort  - Selection Sort

  - Depth-First-Search (DFS)  - Breadth-First-Search (BFS)  - Topologial sort  - Floyd–Warshall algorithm  - Dijkstra's algorithm

  - Patttern Matching  - Boyer–Moore string search  - Knut-Morris-Prat string search

  - Miller-Rabin primality test  - Simple primality test

  - Quick Union  - Union Find  - Weighted Union Find  - Weighted Union Find with Path Compression

  - Longest Increasing Subsequence (LIS)  - Levenshtein Distance  - 0-1 Knapsack Problem

  - TopCoder (www.topcoder.com)  - HackerRank problems & submissions (https://www.hackerrank.com)  - CoderByte challenges (https://coderbyte.com)

Solutions to specific area problems in Computer Science discipline.

Solutions to various challenges published athttps://coderbyte.com

Solutions to various challenges published athttps://hackerrank.com

• Binary Search Tree LCA
• Shortest Path in Unweighted Graph with cycles
• Weighted Path
• PowerSet
• Subset Sum
• Two Sum
• Array Addition

Check out unit test in order to take usage examples.

Sort algorithms factory methods implementation will followfunctional interface. Old school concrete type disclosure available too as well.

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm,serving as a systematic method for placing the elements of an array in order.Developed by Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting.When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

Worst case: О(n^2)Best case: О(n log n)Average: О(n log n)Space: O(n) naive

frompy_algorithms.sortimportnew_quick_sortxs= [0,6,7,8,9,4,5,12,-1]sorting_algorithm=new_quick_sort()sorting_algorithm(xs)#=> [-1, 0, 4, 5, 6, 7, 8, 9, 12]

In computer science, heapsort is a comparison-based sorting algorithm.Heapsort can be thought of as an improved selection sort: like that algorithm,it divides its input into a sorted and an unsorted region, and it iterativelyshrinks the unsorted region by extracting the largest element and movingthat to the sorted region. The improvement consists of the use of a heap data structurerather than a linear-time search to find the maximum.

Worst case: О(n log n)Best case: О(n)Average: О(n log n)Worst case space: O(1)

frompy_algorithms.sortimportnew_heap_sortxs= [0,6,7,8,9,4,5,12,-1]sorting_algorithm=new_heap_sort()sorting_algorithm(xs)#=> [-1, 0, 4, 5, 6, 7, 8, 9, 12]

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort.It can be seen as either a generalization of sorting by exchange (bubble sort) orsorting by insertion (insertion sort). The method starts by sorting pairs of elements far apartfrom each other, then progressively reducing the gap between elements to be compared.Starting with far apart elements, it can move some out-of-place elements into position fasterthan a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants,determining their time complexity remains an open problem.

Worst case: О(n^2)Best case: О(n log n)Average: ~Worst case space: O(n)

frompy_algorithms.sortimportnew_shell_sortxs= [0,6,7,8,9,4,5,12,-1]sorting_algorithm=new_shell_sort()sorting_algorithm(xs)#=> [-1, 0, 4, 5, 6, 7, 8, 9, 12]

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedlysteps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

Worst case: O(n^2)Best case: O(n) (if already sorted)Average: O(n^2)Worst case space: O(1)

frompy_algorithms.sortimportnew_bubble_sortsort=new_bubble_sort()# type: Callable[[List[T]], List[T]]sort([20,15,0,-1,70,-88])#=> [-88, -1, 0, 15, 20, 70]

In computer science, merge sort is an efficient, general-purpose,comparison-based sorting algorithm. Most implementations produce a stable sort,which means that the implementation preserves the input order of equal elements in the sorted output.Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Worst case: О(n)Best case: О(n log n)Average: О(n log n)Worst case space: O(n)

frompy_algorithms.sortimportnew_merge_sortxs= [0,6,7,8,9,4,5,12,-1]sorting_algorithm=new_merge_sort()sorting_algorithm(xs)#=> [-1, 0, 4, 5, 6, 7, 8, 9, 12]

Comb sort is a relatively simple sorting algorithm originally designed byWłodzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey and Richard Box in 1991.Comb sort improves on bubble sort. The basic idea is to eliminate turtles,or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously.Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.

Worst case: О(n^2)Best case: О(n log n)Average: О(n^2)Worst case space: O(1)

frompy_algorithms.sortimportnew_comb_sortxs= [0,6,7,8,9,4,5,12,-1]sorting_algorithm=new_comb_sort()sorting_algorithm(xs)#=> [-1, 0, 4, 5, 6, 7, 8, 9, 12]

In computer science, selection sort is a sorting algorithm,specifically an in-place comparison sort. It has O(n^2) time complexity,making it inefficient on large lists, and generally performs worse than the similar insertion sort.Selection sort is noted for its simplicity, and it has performanceadvantages over more complicated algorithms in certain situations,particularly where auxiliary memory is limited.

Worst case: О(n^2)Best case: О(n^2)Average: О(n^2)Worst case space: O(n)

frompy_algorithms.sortimportnew_selection_sortxs= [0,6,7,8,9,4,5,12,-1]sorting_algorithm=new_selection_sort()sorting_algorithm(xs)#=> [-1, 0, 4, 5, 6, 7, 8, 9, 12]

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop,is a search algorithm that finds the position of a target value within a sorted array.

frompy_algorithms.searchimportnew_binary_search,Searcharray= [0,4,5,6,7,8,9,12]algorithm=new_binary_search()# type: Searchalgorithm.search(array,12)#=> 12algorithm.search(array,6)#=> 6

In computer science, a double-ended queue (dequeue, often abbreviated to deque)is an abstract data type that generalizes a queue, for which elements can be added toor removed from either the front (head) or back (tail)

Deque implementation using doubly-linked list underneath. Operations takingconstant time.

frompy_algorithms.data_structuresimportnew_deque,Dequeds=new_deque()# type: Dequeds.push_back(1)#=> 1ds.push_front(2)#=> 2ds.front#=> 2ds.back#=> 1ds.pop_front()#=> 2ds.size#=> 1

FIFO is an acronym for first in, first out, a method for organizing and manipulating a data buffer,where the oldest (first) entry, or 'head' of the queue, is processed first.

frompy_algorithms.data_structuresimportnew_queue,Queueds=new_queue()# type: Queueds.push(1)ds.push(2)ds.pop()#=> 1ds.pop()#=> 2ds.size#=> 0

In computer science, a stack is an abstract data type that serves as a collection of elements,with two principal operations: push, which adds an element to the collection, and pop,which removes the most recently added element that was not yet removed.The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out).Additionally, a peek operation may give access to the top without modifying the stack.

frompy_algorithms.data_structuresimportnew_stack,Stackds=new_stack()# type: Stackds.push(1)ds.push(2)ds.pop()#=> 2ds.pop()#=> 1ds.size#=> 0

In computer science, a Fibonacci heap is a data structure for priority queue operations,consisting of a collection of heap-ordered trees. It has a better amortized running timethan many other priority queue data structures including the binary heap and binomial heap.Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and publishedthem in a scientific journal in 1987. They named Fibonacci heaps after the Fibonacci numbers,which are used in their running time analysis.

Make a new heap withMax property by supplying functor(a: any, b: any) => c: int

frompy_algorithms.data_structuresimportnew_heap,Heapheap=new_heap(lambdax,y: (x>y)- (x<y)==1)# type: Heap# Push distinct key value pairs to the heapheap.push('Kelly',1)heap.push('Susan',8)heap.push('Ryan',7)# Heap should manage to keep highest key & value on the topheap.next_key#=> 'Susan'heap.pop()#=> 8

frompy_algorithms.data_structuresimportnew_max_heap,Heapheap=new_max_heap()# type: Heapheap.push('Kelly',1)heap.push('Susan',8)heap.push('Ryan',7)# Heap should manage to keep highest key & value on the topheap.next_key#=> 'Susan'heap.max#=> 8heap.pop()#=> 8

frompy_algorithms.data_structuresimportnew_min_heap,Heapheap=new_min_heap()# type: Heapheap.push('One',1)heap.push('Eight',-8)heap.push('Seven',7)# Heap should manage to keep lowest key & value on the topheap.next_key#=> 'Eight'heap.min#=> -8heap.pop()#=> -8

In computer science, a priority queue is an abstract data type which is like aregular queue or stack data structure, but where additionally each element has a "priority"associated with it. In a priority queue, an element with high priority is served beforean element with low priority. If two elements have the same priority,they are served according to their order in the queue.

Example of a Max PQ data structure

frompy_algorithms.data_structuresimportnew_priority_queuepq=new_priority_queue(lambdax,y: (x>y)- (x<y)==1)pq.push('Important',10)pq.push('Not So Important',-2)pq.pop()#=> 'Important'

In computer science, a suffix array is a sorted array of all suffixes of a string.It is a data structure used, among others, in full text indices,data compression algorithms and within the field of bibliometrics.Suffix arrays were introduced by Manber & Myers (1990) as a simple,space efficient alternative to suffix trees. They have independently been discovered byGaston Gonnet in 1987 under the name PAT array (Gonnet, Baeza-Yates & Snider 1992).

frompy_algorithms.data_structuresimportnew_suffix_arrayds=new_suffix_array('python')ds.is_sub_str('py')#=> Trueds.is_sub_str('on')#=> Trueds.is_sub_str('ton')#=> Trueds.is_sub_str('blah')#=> False

In the field of computer science, a topological sort or topological ordering of a directed graph is alinear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.For instance, the vertices of the graph may represent tasks to be performed, and the edges may representconstraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

frompy_algorithms.graphimportnew_directed_graph,topological_sort_f1dag=new_directed_graph()a=dag.insert_vertex('A')b=dag.insert_vertex('B')c=dag.insert_vertex('C')d=dag.insert_vertex('D')e=dag.insert_vertex('E')dag.insert_edge(a,e,None)dag.insert_edge(b,d,None)dag.insert_edge(c,d,None)dag.insert_edge(d,e,None)topological_sort_f1(dag)#=> [#<Vertex(C)>, #<Vertex(B)>, #<Vertex(D)>, #<Vertex(A)>, #<Vertex(E)>]

frompy_algorithms.graphimportnew_undirected_graphfrompy_algorithms.graphnew_dijkstra_shortest_pathfrompy_algorithms.graphreconstruct_dijkstra_path_treegraph=new_undirected_graph()a=graph.insert_vertex('A')b=graph.insert_vertex('B')c=graph.insert_vertex('C')d=graph.insert_vertex('D')e=graph.insert_vertex('E')graph.insert_edge(a,e,10)graph.insert_edge(b,d,2)graph.insert_edge(c,d,3)graph.insert_edge(d,e,12)# Start from vertex "c" and grow the cluster.paths=new_dijkstra_shortest_path(graph,c)assertpaths[c]==0assertpaths[d]==3assertpaths[b]==5assertpaths[e]==15assertpaths[a]==25# Reconstructing all the paths dicovered by algorithmpath_tree=reconstruct_dijkstra_path_tree(graph,c,paths)# Expanding path from vertex "a" to vertex "c" from "path_tree"p=astack= [a]whilep!=c:p=path_tree[p].opposite(p)stack.append(p)assertstack== [a,e,d,c]# The shortest path to reach vertex "a":assertstack== [a,e,d,c]

In computer science, the Boyer–Moore string search algorithm is an efficient string searching algorithm thatis the standard benchmark for practical string search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977.The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text).It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches.The Boyer-Moore algorithm uses information gathered during the preprocess step to skip sections of the text,resulting in a lower constant factor than many other string search algorithms.

frompy_algorithms.stringsimportnew_boyer_moore_findalgorithm=new_boyer_moore_find()substr='abcd'algorithm('foo'+substr+'bar',substr)# => 3

A primality test is an algorithm for determining whether an input number is prime.Among other fields of mathematics, it is used for cryptography.Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input numberis prime or not. Factorization is thought to be a computationally difficult problem, whereas primalitytesting is comparatively easy (its running time is polynomial in the size of the input).Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite.Therefore, the latter might be called compositeness tests instead of primality tests.

The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime,similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version, due to Gary L. Miller, is deterministic,but the correctness relies on the unproven Extended Riemann hypothesis; Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm.

frompy_algorithms.primality_testsimportnew_miller_rabin_primality_testalgorithm=new_miller_rabin_primality_test()algorithm(199)#=> True, 199 is a prime numberalgorithm(4)#=> False, 4 % 2 == 0, therefore, 4 is not a prime number.

The test itself is simple and straightforward, but would work very slow on quite big primes.

frompy_algorithms.primality_testsimportnew_simple_primality_testalgorithm=new_simple_primality_test()algorithm(32416190071)#=> True, 32416190071 is a prime numberalgorithm(4)#=> False, 4 % 2 == 0, therefore, 4 is not a prime number.

In computer science, mathematics, management science, economics and bioinformatics,dynamic programming (also known as dynamic optimization) is a method for solving a complex problemby breaking it down into a collection of simpler subproblems, solving each of those subproblemsjust once, and storing their solutions. The next time the same subproblem occurs,instead of recomputing its solution, one simply looks up the previously computed solution,thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.(Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters,so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called "memoization".

In information theory, Linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences.Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.It is named after Vladimir Levenshtein, who considered this distance in 1965.Levenshtein distance may also be referred to as edit distance, although that term may also denote a larger family of distance metrics.

It is closely related to pairwise string alignments.

frompy_algorithms.stringsimportnew_levenshtein_distancedistance=new_levenshtein_distance(list('Moon'),list("Moore"))assert2==distance

Bug reports and pull requests are welcome on GitHub athttps://github.com/rlishtaba/py-algorithms. This project is intended to be a safe, welcoming space for collaboration, and contributors are expected to adhere to theContributor Covenant code of conduct.

The library is available as open source under the terms of theMIT License.