Popular recipes tagged "algorithms" but not "algorithm"

Python A* Pathfinding (With Binary Heap) (Python)

2014-08-06T10:03:01-07:00

Python recipe 578919 by Christian Careaga (algorithms, binary_search). Revision 3.

Implementation of the A-star Pathfinding algorithm in Python, using Binary heap to sort the open list

edge-coloring of a bipartite graph (Python)

2015-07-30T13:40:41-07:00

Python recipe 579088 by Praveen (algorithms).

Konig's theorem tells us that every bipartite graph with maximum vertex-degree d can be edge-colored with just d colors. This recipe relies on a previous recipe by D.Eppstein (123641) : "Hopcroft-Karp bipartite matching".

Simple Linear Regression with Pure Python (Python)

2014-07-31T15:55:15-07:00

Python recipe 578914 by Chaobin Tang (唐超斌) (algorithms, machine_learning, python, regression).

Linear regression is a very useful and simple to understand way for predicting values, given a set of training data. The outcome of the regression is a best fitting line function, which, by definition, is the line that minimizes the sum of the squared errors (When plotted on a 2 dimensional coordination system, the errors are the distance between the actual Y' and predicted Y' on the line.) In machine learning, this line equation Y' = b*x + A is solved using Gradient Descent to gradually approach to it. Also, there is a statistical approach that directly solves this line equation without using an iterative algorithm.

This recipe is a pure Python implementation of this statistical algorithm. It has no dependencies.

If you have pandas and numpy, you can test its result by uncommenting the assert lines.

The Bentley-Knuth problem and solutions (Python)

2014-03-15T23:46:59-07:00

Python recipe 578851 by Vasudev Ram (algorithms, python, text_processing).

This is a program Jon Bentley asked Donald Knuth to write, and is one that’s become familiar to people who use languages with serious text-handling capabilities: Read a file of text, determine the n most frequently used words, and print out a sorted list of those words along with their frequencies. I wrote 2 solutions for it earlier, in Python and in Unix shell. Also see the comment by a user on the post, giving another solution.

Priority queue dictionary (Python)

2013-08-25T00:23:12-07:00

Python recipe 578643 by Nezar Abdennur (algorithms, dictionary, heap, heapq, pqdict, priority_queue). Revision 4.

An indexed priority queue implemented in pure python as a dict-like class. It is a stripped-down version of pqdict. A Priority Queue Dictionary maps dictionary keys (dkeys) to updatable priority keys (pkeys).

The priority queue is implemented as a binary heap, which supports:

O(1) access to the top priority element
O(log n) removal of the top priority element
O(log n) insertion of a new element

In addition, an internal dictionary or "index" maps dictionary keys to the position of their entry in the heap. This index is maintained as the heap is manipulated. As a result, a PQ-dict also supports:

O(1) lookup of an arbitrary element's priority key
O(log n) removal of an arbitrary element
O(log n) updating of an arbitrary element's priority key

A data structure like this can be used to drive simulations, schedulers, certain greedy algorithms, merging streams of sorted data, and other applications where priorities may need to be changed frequently.

A simple KD Tree example with custom Euclidean distance ball query. (Python)

2013-01-24T10:28:24-08:00

Python recipe 578434 by alexander baker (algorithms, python).

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

http://en.wikipedia.org/wiki/K-d_tree

Averaging Literal Numbers (Python)

2012-12-06T13:44:42-08:00

Python recipe 578365 by Stephen Chappell (algorithms, demonstration, numbers).

One program that a teacher may assign to beginning programming students would be to take a list of numbers and average them together. This recipe does just that and is designed to be easy to read and follow, showing what is possible with a few lines of Python.

Converts from decimal to any base ( between 2 and 26 ) (Python)

2011-02-24T00:33:07-08:00

Python recipe 577586 by Shashwat Anand (algorithms, base).

This function takes in any base-10 integer and returns the string representation of that number in its specified base-n form. The code was inspired from http://code.activestate.com/recipes/65212-convert-from-decimal-to-any-base-number/ , thereby improving upon it.

2-3 Tree (Python)

2011-10-08T21:46:03-07:00

Python recipe 577898 by Boris (2_3tree, algorithms, data, python, structure, tree).

My implementation of 2-3 Trees on python

Caching decorator with timeout, selective invalidation (Python)

2005-11-05T05:47:03-08:00

Python recipe 442513 by Greg Steffensen (algorithms). Revision 5.

A caching decorator that garbage collects in a separate thread (for performance), allows each cached function to (optionally) set a custom maximum age for entries, and allows individual cache entries to be selectively invalidated.

get all possible combinations of characters given a string (Python)

2011-08-15T04:15:42-07:00

Python recipe 577842 by Yang (algorithms, permutation, string).

This will give a result that is more than a permutation, but all possible combinations. An example is when input is 'abc', the output would be: a,ab,abc,ac,acb,b,ba,bac,bc,bca,c,ca,cab,cb,cba

Compare algorithms for heapq.smallest (Python)

2011-12-25T23:41:23-08:00

Python recipe 577573 by Raymond Hettinger (algorithms, benchmark, heaps, performance). Revision 3.

General purpose technique for counting comparisons in various searching and sorting applications.

Python Binary Search Tree (Python)

2011-08-08T00:15:09-07:00

Python recipe 577830 by sivarama sarma (algorithms, maximum, minimum, search, sort).

A data structure that holds a sorted collection of values, and supports efficient insertion, deletion, sorted iteration, and min/max finding. Values may sorted either based on their natural ordering, or on a key function (specified as an argument to the search tree's constructor). The search tree may contain duplicate values (or multiple values with equal keys) -- the ordering of such values is undefined.

This implementation was made with efficiency in mind. In particular, it is more than twice as fast as the other native-Python implementations I tried (which all use objects to store search tree nodes).

SleepSort (Timer version) (Python)

2011-06-18T05:37:06-07:00

Python recipe 577762 by wong2 (algorithms, interest, sort).

Python version sleep sort by using threading.Timer

Python Binary Search Tree (Python)

2011-01-10T02:27:08-08:00

Python recipe 577540 by Edward Loper (algorithms, maximum, minimum, search, sort). Revision 2.

Simple graph algorithms with a modular design (Python)

2011-04-21T13:40:32-07:00

Python recipe 577668 by jimmy2times (algorithms, breadth, depth, directed, first, graph, object, oriented, python, search, theory, undirected, visit). Revision 7.

The purpose of this recipe is to look at algorithmic graph theory from an object-oriented perspective.

A graph is built on top of a dictionary indexed by its vertices, each item being the set of neighbours of the key vertex. This ensures that iterating through the neighbours of a vertex is still efficient in sparse graphs (as with adjacency lists) while at the same time checking for adjacency is expected constant-time (as with the adjacency matrix).

Any valid class of graph must implement the interface defined by AbstractGraph.

A generic search algorithm takes as input a graph, source and target vertices and a queue. A queue must implement the methods Q.get(), Q.put() and Q.empty() in such a way to get the desired order in visiting the vertices.

Given this pattern, breadth-first and depth-first search are essentially defined by the corresponding expansion policies: the first one uses an actual FIFO queue, the second one a LIFO queue (or stack).

Aggregates using groupby, defaultdict and Counter (Python)

2011-02-07T15:38:09-08:00

Python recipe 577535 by N N (algorithms). Revision 2.

How to emulate SQL aggregate functions AVG, COUNT, MAX, MIN and SUM on csv type data files using tools from the standard library.

An interval mapping data structure (Python)

2010-12-23T12:51:27-08:00

Python recipe 577515 by Matteo Dell'Amico (algorithms, interval, mapping).

This structure is a kind of dictionary which allows you to map data intervals to values. You can then query the structure for a given point, and it returns the value associated to the interval which contains the point. Boundary values don't need to be an integer.

In this version, the excellent blist library by Daniel Stutzbach is used for efficiency. By using the collections.MutableMapping abstract base class, the whole signature of mappings is supported.

Eight queen problem (Python)

2013-05-10T03:44:56-07:00

Python recipe 577438 by Thomas Lehmann (algorithms, queen). Revision 5.

Task:

Think of a chess field 8x8.
Place 8 queens in a way that no one threaten another one.

Intention:

Writing an algorithm to provide all solutions
Adjusting the algorithm in a way that it can handle chess fields by other sizes n x n.

Changes:

Revision 5:
- can run providing "n" via command line parameter and
- run half of board adding the other solutions by mirroring (12x12 takes 4 seconds instead of 8 on my slow notebook)
...

Other languages:

My recipe 578497 for JavaScript
...

Dijkstra's algorithm for shortest paths (Python)

2010-08-02T13:03:45-07:00

Python recipe 577343 by poromenos (algorithms).

Dijkstra(G,s) finds all shortest paths from s to each other vertex in the graph, and shortestPath(G,s,t) uses Dijkstra to find the shortest path from s to t. Uses the priorityDictionary data structure (Recipe 117228) to keep track of estimated distances to each vertex.