http://code.activestate.com/recipes/tags/algorithms/top/2011-01-10T02:27:08-08:00ActiveState Code Recipes2004-02-12T07:05:02-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/259173-groupby/

<p style="color: grey"> Python recipe 259173 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 5. </p> <p>Guido inspired SQL-like GROUPBY class that also encapsulates the logic in a Unix-like "sort | uniq".</p>

2003-03-20T10:54:20-08:00Ulrich Hoffmannhttp://code.activestate.com/recipes/users/1056747/http://code.activestate.com/recipes/190465-generator-for-permutations-combinations-selections/

<p style="color: grey"> Python recipe 190465 by <a href="/recipes/users/1056747/">Ulrich Hoffmann</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>Permutations and combinations are often required in algorithms that do a complete search of the solution space. They are typically rather large so it's best not to compute them entirely but better to lazily generate them. This recipe uses Python 2.2 generators to create appropriate generator objects, that can be use for example as ranges in for loops.</p>

2011-01-10T02:27:08-08:00Edward Loperhttp://code.activestate.com/recipes/users/2637812/http://code.activestate.com/recipes/577540-python-binary-search-tree/

<p style="color: grey"> Python recipe 577540 by <a href="/recipes/users/2637812/">Edward Loper</a> (<a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/maximum/">maximum</a>, <a href="/recipes/tags/minimum/">minimum</a>, <a href="/recipes/tags/search/">search</a>, <a href="/recipes/tags/sort/">sort</a>). Revision 2. </p> <p>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.</p> <p>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).</p> <p>See also: <a href="http://en.wikipedia.org/wiki/Binary_search_tree">http://en.wikipedia.org/wiki/Binary_search_tree</a>, <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">http://en.wikipedia.org/wiki/A*_search_algorithm</a></p>

2010-12-25T23:36:35-08:00FB36http://code.activestate.com/recipes/users/4172570/http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/

<p style="color: grey"> C++ recipe 577457 by <a href="/recipes/users/4172570/">FB36</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/game/">game</a>, <a href="/recipes/tags/graph/">graph</a>, <a href="/recipes/tags/graphs/">graphs</a>, <a href="/recipes/tags/routes/">routes</a>). Revision 4. </p> <p>A-star (A*) is a shortest path algorithm widely used for RTS games, GPS navigation etc.</p>

2007-02-09T18:01:54-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/491285-iterator-merge/

<p style="color: grey"> Python recipe 491285 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 3. </p> <p>Memory efficient multi-way iterator merge.</p>

2006-02-26T15:02:54-08:00Crutcher Dunnavanthttp://code.activestate.com/recipes/users/2792865/http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/

<p style="color: grey"> Python recipe 474088 by <a href="/recipes/users/2792865/">Crutcher Dunnavant</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>This decorator implements tail call optimization through stack introspection.</p>

2009-03-28T23:32:08-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/393090-binary-floating-point-summation-accurate-to-full-p/

<p style="color: grey"> Python recipe 393090 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 5. </p> <p>Completely eliminates rounding errors and loss of significance due to catastrophic cancellation during summation. Achieves exactness by keeping full precision intermediate subtotals. Offers three alternative approaches, each using a different technique to store exact subtotals.</p>

2004-11-07T01:08:26-08:00Douglas Bagnallhttp://code.activestate.com/recipes/users/1629020/http://code.activestate.com/recipes/326576-language-detection-using-character-trigrams/

<p style="color: grey"> Python recipe 326576 by <a href="/recipes/users/1629020/">Douglas Bagnall</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>The Trigram class can be used to compare blocks of text based on their local structure, which is a good indicator of the language used. It could also be used within a language to discover and compare the characteristic footprints of various registers or authors. As all n-gram implementations should, it has a method to make up nonsense words.</p>

2007-12-05T01:25:49-08:00Noah Spurrierhttp://code.activestate.com/recipes/users/103276/http://code.activestate.com/recipes/146262-finite-state-machine-fsm/

<p style="color: grey"> Python recipe 146262 by <a href="/recipes/users/103276/">Noah Spurrier</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>This recipe shows a Finite State Machine (FSM) that can be used for small parsing tasks. The code is quite simple. The bulk of it is comments. In addition to state this FSM also maintains a user defined "memory". So this FSM is a Push-down Automata (PDA) since a PDA is a FSM + memory. This module contains an example function that demonstrates a simple RPN expression evaluator.</p>

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>

2001-08-17T00:50:23-07:00Dinu Ghermanhttp://code.activestate.com/recipes/users/124101/http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/

<p style="color: grey"> Python recipe 66527 by <a href="/recipes/users/124101/">Dinu Gherman</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>This simple code calculates the convex hull of a set of 2D points and generates EPS files to visualise them. The algorithm was taken from a textbook on Computional Geometry.</p>

2007-08-10T14:27:52-07:00Robin Parmarhttp://code.activestate.com/recipes/users/99666/http://code.activestate.com/recipes/526619-friendly-readable-id-strings/

<p style="color: grey"> Python recipe 526619 by <a href="/recipes/users/99666/">Robin Parmar</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 3. </p> <p>One often needs unique ID strings to tag processes, threads, files or anything else that might be created in quantity. Traditionally these are created based on PIDs or similar system values. But it is not easy to visually recognise these strings, which makes debugging more difficult than it need be. This recipe creates readable and pronounceable ID strings that are much easier to work with.</p>

2006-07-26T01:23:58-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/496908-data-mining-with-neural-nets/

<p style="color: grey"> Python recipe 496908 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>Apply the IAC (interactive-competition-and-activation) model to analyzing a database.</p>

2005-05-16T06:20:36-07:00Oren Tiroshhttp://code.activestate.com/recipes/users/2033964/http://code.activestate.com/recipes/414283-frozen-dictionaries/

<p style="color: grey"> Python recipe 414283 by <a href="/recipes/users/2033964/">Oren Tirosh</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>A frozendict is a dictionary that cannot be modified after being created - but it is hashable and may serve as a member of a set or a key in a dictionary.</p>

2006-09-13T12:28:57-07:00John Nielsenhttp://code.activestate.com/recipes/users/135654/http://code.activestate.com/recipes/305304-sorting-old-to-new-python-24-style-heapqbisectlist/

<p style="color: grey"> Python recipe 305304 by <a href="/recipes/users/135654/">John Nielsen</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>Python 2.4 has added a new feature to handle the problem where you needed to do a sort based off of part of the data. In effect, it has simplified the Schwartzian Transform (which I learned many years ago from an perl article written by Randall Schwartz). The following code will start with the older style python sorting approaches, and then show the bisect and heapq modules, and finally the key,cmp,reverse methods newly added to sort. The sort method of the list is an in-place sort. There is also a new sorted() function which returns a copy of the list sorted for you.</p>

2004-11-30T07:57:31-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/259174-bag-collection-class/

<p style="color: grey"> Python recipe 259174 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 6. </p> <p>Implement Smalltalk's bag class (similar to MultiSets in C++ or bag's in Objective C or Haskell's Edison module).</p>

2007-05-19T07:07:23-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/230113-implementation-of-sets-using-sorted-lists/

<p style="color: grey"> Python recipe 230113 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>Inspired by Py2.3's TimSort, this implementation of sets.py uses sorted lists instead of dictionaries. For clumped data patterns, the set operations can be super-efficient (for example, two sets can be determined to be disjoint with only O(n) comparisons). Also note, that the set elements are <em>not</em> required to be hashable; this provides a great deal more freedom than dictionary based implementations.</p>

2008-01-18T19:51:11-08:00Sean Rosshttp://code.activestate.com/recipes/users/761068/http://code.activestate.com/recipes/199121-a-simple-genetic-algorithm/

<p style="color: grey"> Python recipe 199121 by <a href="/recipes/users/761068/">Sean Ross</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p>

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>

2001-06-06T11:03:36-07:00Hamish Lawsonhttp://code.activestate.com/recipes/users/98049/http://code.activestate.com/recipes/59892-testing-if-a-variable-is-defined/

<p style="color: grey"> Python recipe 59892 by <a href="/recipes/users/98049/">Hamish Lawson</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>You want to take different courses of action based on whether a variable is defined or not.</p>