ExAlgo
ExAlgo
is a collection of data structures and algorithms implemented in Elixir. This is the authors attempt to see algorithms through Elixir's lens.
The sole purpose of this is to use as a learning tool for algorithms in a functional language set-up. I am also thinking of using this to host some algorithms that could come in handy while solving Advent of Code. Almost all algorithms mentioned here have well tested and production ready libraries so I see little use that anyone would want to use this for anything serious.
Development
Download this repo and get the dependencies with mix deps.get
. Go to iex -S mix
to try out the algorithms in the REPL. mix test
runs all the tests.
Detailed Documentation
TODO - Add ex_doc pages with detailed explanations of each categories.
Catalogue
Graph
Name | Implementation | Test | Benchmark | Link | Note |
---|
Heap
Name | Implementation | Test | Benchmark | Link | Note |
---|
List
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Linked List | linked_list.ex | Yes | No | ||
Circular List | circular_list.ex | Yes | No | ||
BidirectionalList | bidirectional_list.ex | Yes | No | WIP | |
Maximum Subarray Sum | algorithms.ex | Yes | No | Kadane's Algorithm |
Functional/Immutable
Name | Implementation | Test | Benchmark | Link | Note |
---|
Queue
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Queue | queue.ex | Yes | No |
Search
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Binary Search | binary_search.ex | Yes | No |
Set
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Disjoint Set | disjoint_set.ex | Yes | No |
Sort
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Bubble Sort | exchange.ex | Yes | No | ||
Insertion Sort | insertion.ex | Yes | No | ||
Merge Sort | merge.ex | Yes | No | ||
Pigeonhole Sort | distribution.ex | Yes | No | ||
Quick Sort | exchange.ex | Yes | No | ||
Selection Sort | selection.ex | Yes | No |
Stack
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Stack | stack.ex | Yes | No | ||
Min-Max Stack | min_max_stack.ex | Yes | No |
String
Name | Implementation | Test | Benchmark | Link | Note |
---|
Tree
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Binary Search Tree | binary_search_tree.ex | Yes | No | ||
Tree Traversals | traversal.ex | Yes | No |
Counting
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Permutations | combinatorics.ex::permutations | Yes | No | Naive | |
Combinations | combinatorics.ex::combinations | Yes | No | Naive |
Trie
Name | Implementation | Test | Benchmark | Link | Note |
---|
Dynamic Programming
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Subset Sum | subset_sum.ex | Yes | No | FIXME: Not all subsets are listed. Need to work on that. |
Numbers
Name | Implementation | Test | Benchmark | Link | Note |
---|---|---|---|---|---|
Chinese Remainder Theorem | chinese_remainder.ex | Yes | No | ||
Catalan Numbers (Recursive) | catalan.ex::recursive | Yes | No | ||
Catalan Numbers (Dynamic) | catalan.ex::dp | Yes | No | ||
Divisors | arithmetics.ex::divisors | Yes | No |