algorithms.py
algorithms.py copied to clipboard
Algorithm playground in Python 3
algorithms.py
A port of @sagivo's algorithms in Python 3
Problems
Problem | Solution |
---|---|
Dijkstra's algorithm for finding the shortest path | dijkstra.py |
Newton's method for finding the square root of a number | sqrt.py |
Binary search algorithm | binary_search.py |
Longest increasing subsequence | lis.py |
Longest common subsequence | lcs.py |
Quicksort | quicksort.py |
Mergesort | mergesort.py |
Counting sort | counting_sort.py |
Shellsort | TODO |
Mix and combine sets of cells to list all possible combinations | mix_sets.py |
Finding all combinations of well-formed brackets | well_formed_brackets.py |
Phonewords | phonewords.py |
Permutation | permutation.py |
Finding the power set of a given set | power_set.py |
Find the next higher number that has the same set of digits | same_digits_next_bigger.py |
[Find the minimum insertions needed to form a Palindrome](from http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/) | palindrome_insertions.py |
Knuth–Morris–Pratt algorithm | kmp.py |
Conway's Game of Life | game_of_life.py |
Knapsack problem | TODO |
Goals
- Recursion over imperative looping constructs such as
for
/while
-loops (1) - Expressions over stateful methods and mutations (whenever possible)
Neither is easy to achive in OO, however, I believe mutability should be opt-in, not the other way around.
Notes:
- Recursion is not generally considered a good practice in Python. Python is not a functional programming language, and there is no TCO support in CPython after all. The focus here is, in fact, more on the algorithms despite being implemented in Python.
How to run tests
All tests can be found in tests.py. Run the following command to test them.
python -m tests
Versions tested
- Python 3.2
- Python 3.3
- Python 3.4
TODO
- More problems
- Further analysis/optimisation
Contributions
Please feel free to submit an issue or pull request for any bugs you may find or algorithms incorrectly implemented.
License
GNU GPLv3