Popular recipes by David Eppstein http://code.activestate.com/recipes/users/218935/2003-11-13T23:19:20-08:00ActiveState Code RecipesGenerator for integer partitions (Python)
2003-08-27T14:02:53-07:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/218332-generator-for-integer-partitions/
<p style="color: grey">
Python
recipe 218332
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>A "partition" is a way of representing a given integer as a sum of zero or more positive integers, e.g. the partitions of 4 are 1+1+1+1, 1+1+2, 2+2, 1+3, and 4. This recipe uses simple generators recursively to produce a stream of all partitions of its argument. Each partition is represented as a sorted list of the numbers to be summed, e.g. [1,1,1,1], [1,1,2], [2,2], [1,3], [4].</p>
Breadth first traversal of tree (Python)
2003-10-31T15:34:40-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/231503-breadth-first-traversal-of-tree/
<p style="color: grey">
Python
recipe 231503
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
Revision 2.
</p>
<p>Uses a recursively called simple generator (with the same arguments as the outer call!) to traverse a tree in breadth first order.</p>
LaTeX codec (Python)
2003-11-13T23:19:20-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/252124-latex-codec/
<p style="color: grey">
Python
recipe 252124
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/text/">text</a>).
</p>
<p>Codec for converting unicodes to LaTeX markup and vice versa.</p>
Maximum cardinality matching in general graphs (Python)
2003-09-12T21:54:02-07:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs/
<p style="color: grey">
Python
recipe 221251
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
Revision 2.
</p>
<p>This is an implementation of Edmonds' blossom-contraction algorithm for maximum cardinality matching in general graphs. It's maybe a little long and complex for the recipe book, but I hope it will spare someone else the agony of implementing it themselves.</p>
Range minima and least common ancestors (Python)
2003-11-13T23:10:41-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/252123-range-minima-and-least-common-ancestors/
<p style="color: grey">
Python
recipe 252123
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>Data structures for solving the following two problems:</p>
<ul>
<li><p>Range minimization: given an array X of data, quickly find min(X[i:j]) for different ranges i:j.</p></li>
<li><p>Least common ancestors: given a tree, quickly find the lowest tree node that is an ancestor of all of a given set of nodes.</p></li>
</ul>
<p>Both problems are solved by data structures that take linear time and space to set up, after which queries can be answered in constant time.</p>
Dijkstra's algorithm for shortest paths (Python)
2002-04-04T12:38:22-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
<p style="color: grey">
Python
recipe 119466
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>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 (<a href="http://code.activestate.com/recipes/117228/">Recipe 117228</a>) to keep track of estimated distances to each vertex.</p>
Self-recursive generators (Python)
2003-09-13T15:06:06-07:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/221457-self-recursive-generators/
<p style="color: grey">
Python
recipe 221457
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>For a function without arguments, calling itself recursively is a quick way to get into an infinite loop. But for a generator, it can actually be useful...here are some simple numerical examples.</p>
Sieve of Eratosthenes (Python)
2002-03-01T18:21:25-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/117119-sieve-of-eratosthenes/
<p style="color: grey">
Python
recipe 117119
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
Revision 2.
</p>
<p>Computes an infinite sequence of primes using simple generators. A Python dictionary is used to mark multiples of the generated primes, according to the Sieve of Eratosthenes.</p>
Knuth-Morris-Pratt string matching (Python)
2002-03-01T23:49:23-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/117214-knuth-morris-pratt-string-matching/
<p style="color: grey">
Python
recipe 117214
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/search/">search</a>).
</p>
<p>This is an implementation of the Knuth-Morris-Pratt algorithm for finding copies of a given pattern as a contiguous subsequence of a larger text. Since KMP accesses the text only sequentially, it is natural to implement it in a way that allows the text to be an arbitrary iterator. After a preprocessing stage which takes time linear in the length of the pattern, each text symbol is processed in constant amortized time.</p>
Hopcroft-Karp bipartite matching (Python)
2002-04-27T16:53:22-07:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/123641-hopcroft-karp-bipartite-matching/
<p style="color: grey">
Python
recipe 123641
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>Takes as input a bipartite graph in a variation of Guido van Rossum's dictionary-of-lists format, and outputs both a maximum matching (largest possible set of nonadjacent edges) and a maximum independent set (largest possible set of nonadjacent vertices). The running time in the worst case is O(E sqrt(V)) but for many graphs it runs faster due to doing fewer than the worst case number of iterations.</p>
Priority dictionary (Python)
2002-03-08T22:09:16-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/117228-priority-dictionary/
<p style="color: grey">
Python
recipe 117228
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>This data structure acts almost like a dictionary, with two modifications: First, D.smallest() returns the value x minimizing D[x]. For this to work correctly, all values D[x] stored in the dictionary must be comparable. Second, iterating "for x in D" finds and removes the items from D in sorted order. Each item is not removed until the next item is requested, so D[x] will still return a useful value until the next iteration of the for-loop.</p>
Convex hull and diameter of 2d point sets (Python)
2003-10-16T18:44:57-07:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/117225-convex-hull-and-diameter-of-2d-point-sets/
<p style="color: grey">
Python
recipe 117225
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
Revision 2.
</p>
<p>Returns the convex hull (separated into upper and lower chains of vertices) and the diameter (farthest pair of points), given input consisting of a list of 2d points represented as pairs (x,y). The convex hull algorithm is Graham's scan, using a coordinate-based sorted order rather than the more commonly seen radial sorted order. A rotating calipers algorithm generates candidate pairs of vertices for the diameter calculation. Care was taken handling tricky cases such as pairs of points with the same x-coordinate and colinear triples of points.</p>
Dendrogram drawing (Python)
2002-07-13T21:17:10-07:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/139422-dendrogram-drawing/
<p style="color: grey">
Python
recipe 139422
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/text/">text</a>).
</p>
<p>This recipe draws a dendrogram (horizontal format used for evolutionary trees), as ASCII text, given as input a binary tree in the form of a tuple for each tree node. Tree leaves can be any Python object other than a length-2 tuple, and are converted to strings in the output. Tree nodes at the same distance from the root will line up at the same column, with the distance between tree levels controlled by an optional "sep" parameter. The algorithm works by a straightforward inorder traversal, keeping some simple data structures to keep track of the tree edges that need to be drawn on each output line. Its output is via print statements but it could easily be modified to send its output lines to any other kind of stream.</p>
SMAWK totally monotone matrix searching algorithm (Python)
2002-03-17T18:04:31-08:00David Eppsteinhttp://code.activestate.com/recipes/users/218935/http://code.activestate.com/recipes/117244-smawk-totally-monotone-matrix-searching-algorithm/
<p style="color: grey">
Python
recipe 117244
by <a href="/recipes/users/218935/">David Eppstein</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>This algorithm takes as input a function for computing matrix values, and searches for the position of maximum value in each row. The matrix must satisfy the "totally monotone" property: in each submatrix (in particular each 2x2 submatrix) the positions of the maxima must move leftward as you go down the rows. The algorithm uses this property to greatly reduce the number of matrix elements evaluated, compared to a naive algorithm that explicitly constructs the matrix.</p>
<p>As a simple example, we apply the algorithm to finding nearest neighbors in B for each point in A, where B may be distributed arbitrarily in space but the points of A lie along a single line. Using SMAWK for this problem takes only linear time if the input is already sorted.</p>