http://code.activestate.com/recipes/tags/algorithms/views/2014-03-03T18:09:00-08:00ActiveState Code Recipes2001-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>

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>

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-04-06T00:54:02-07:00Tim Petershttp://code.activestate.com/recipes/users/98361/http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/

<p style="color: grey"> Python recipe 52560 by <a href="/recipes/users/98361/">Tim Peters</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>The fastest way to remove duplicates from a sequence depends on some pretty subtle properties of the sequence elements, such as whether they're hashable, and whether they support full comparisons. The unique() function tries three methods, from fastest to slowest, letting runtime exceptions pick the best method available for the sequence at hand.</p>

2006-06-23T21:53:28-07:00Wensheng Wanghttp://code.activestate.com/recipes/users/1513433/http://code.activestate.com/recipes/366178-a-fast-prime-number-list-generator/

<p style="color: grey"> Python recipe 366178 by <a href="/recipes/users/1513433/">Wensheng Wang</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 5. </p> <p>This is a fast prime number list generator using sieve algorithm. This function return a list of prime numbers which &lt;= argument.</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>

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>

2004-07-20T07:59:27-07:00Foo Bearhttp://code.activestate.com/recipes/users/181960/http://code.activestate.com/recipes/286239-binary-ordered-tree/

<p style="color: grey"> Python recipe 286239 by <a href="/recipes/users/181960/">Foo Bear</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>A simple example demonstrating the construction of binary trees.</p>

2005-11-05T05:47:03-08:00Greg Steffensenhttp://code.activestate.com/recipes/users/2649990/http://code.activestate.com/recipes/442513-caching-decorator-with-timeout-selective-invalidat/

<p style="color: grey"> Python recipe 442513 by <a href="/recipes/users/2649990/">Greg Steffensen</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 5. </p> <p>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.</p>

2004-09-02T01:40:58-07:00Brian Quinlanhttp://code.activestate.com/recipes/users/118989/http://code.activestate.com/recipes/303060-group-a-list-into-sequential-n-tuples/

<p style="color: grey"> Python recipe 303060 by <a href="/recipes/users/118989/">Brian Quinlan</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>This function returns a list of n-tuples from a single "flat" list.</p>

2003-02-16T14:25:05-08:00yaipa haahttp://code.activestate.com/recipes/users/519352/http://code.activestate.com/recipes/181064-using-a-dictionary-in-place-of-a-switch-statement/

<p style="color: grey"> Python recipe 181064 by <a href="/recipes/users/519352/">yaipa haa</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>Description: Rock, Scissors, Paper Game. Shows a clean way of implementing a 'switch' statement in Python via a dictionary container. The dictionary is made up of known 'named states' that are tested in sequence for their current 'state'.</p>

2005-09-01T06:40:50-07:00Allen Downeyhttp://code.activestate.com/recipes/users/2523263/http://code.activestate.com/recipes/440502-a-dictionary-with-multiple-values-for-each-key/

<p style="color: grey"> Python recipe 440502 by <a href="/recipes/users/2523263/">Allen Downey</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). </p> <p>I often find myself wanting to accumulate all the values for a given key in a list. The mdict class provides a simple implementation of this feature.</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>

2014-03-03T18:09:00-08:00Karl Schärlundhttp://code.activestate.com/recipes/users/99773/http://code.activestate.com/recipes/81188-binary-search/

<p style="color: grey"> Python recipe 81188 by <a href="/recipes/users/99773/">Karl Schärlund</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 2. </p> <p>A straightforward implementation of the binary search algorithm.</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>

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>

2003-04-12T19:29:43-07:00Brian Chinhttp://code.activestate.com/recipes/users/1095547/http://code.activestate.com/recipes/194364-the-markov-chain-algorithm/

<p style="color: grey"> Python recipe 194364 by <a href="/recipes/users/1095547/">Brian Chin</a> (<a href="/recipes/tags/algorithms/">algorithms</a>). Revision 3. </p> <p>A classic algorithm which can produce entertaining output, given a sufficiently large input</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>

2010-12-26T08:31:16-08:00FB36http://code.activestate.com/recipes/users/4172570/http://code.activestate.com/recipes/577519-a-star-shortest-path-algorithm/

<p style="color: grey"> Python recipe 577519 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/graph/">graph</a>, <a href="/recipes/tags/routes/">routes</a>). Revision 3. </p> <p>A-star (A*) Shortest Path Algorithm</p>