Latest recipes tagged "algorithms"

Reversi Othello (Python)

2016-09-19T18:03:09-07:00

Python recipe 580698 by FB36 (ai, algorithm, algorithms, game, games).

Reversi/Othello Board Game using Minimax, Alpha-Beta Pruning, Negamax, Negascout algorithms.

Hopfield Artificial Neural Network (C++)

2016-07-03T21:58:49-07:00

C++ recipe 580688 by Jay baller (ai, algorithm, algorithms, artificial_intelligence, neural_network).

(Discrete (Binary)) Hopfield Artificial Neural Network (ANN).

For more info see:

http://en.wikipedia.org/wiki/Hopfield_net

http://www.scholarpedia.org/article/Hopfield_network

Computing simple list functions recursively (Python)

2016-03-01T20:41:13-08:00

Python recipe 580617 by Vasudev Ram (algorithm, algorithms, lists, python, python2, recursion, recursive).

This recipe shows how to compute some simple list functions (functions that operate on lists) using simple recursive algorithms. Simple non-recursive algorithms exist for these tasks; this recipe is just for illustrative purposes. However, the principles described can be used for more complex recursive algorithms, for which non-recursive algorithms might be more complex than the recursive ones.

Infix Expression Evaluation (Python)

2015-11-08T05:08:26-08:00

Python recipe 579123 by FB36 (algorithm, algorithms, math, mathematics, stack).

Infix expression evaluation using two stacks.

Simple Infix Expression Evaluation (Python)

2015-11-07T18:44:05-08:00

Python recipe 579122 by FB36 (algorithm, algorithms, math, mathematics, stack).

Simple infix expression evaluation using a stack.

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".

Flattening an arbitrarily nested list in Python (Python)

2014-10-05T21:44:45-07:00

Python recipe 578948 by Vasudev Ram (algorithm, algorithms, flatten, list, lists, python).

This is a recipe to flatten a Python list which may have nested lists as items within it. It works for lists that have a maximum depth of nesting roughly equal to the recursion depth limit of Python, which is set to 1000 by default, though it can be increased with sys.setrecursionlimit().

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

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

Knight's Tour Map using Warnsdorff's Algorithm (Python)

2012-12-18T01:05:51-08:00

Python recipe 578386 by FB36 (algorithm, algorithms, graphics, math, mathematics, pil).

Solves Knight's Tour Problem using Warnsdorff's Algorithm for every square on the chessboard of arbitrary size.

It colors each initial square with a color that depends on the final square coordinates. (This is a method used to create fractals.) Many different formulas maybe used for coloring (based on abs/rel x/y/dist/ang).

Calculating each tour in full creates a highly chaotic image (and takes hours). So I added maxItPercent to cut-off tours earlier. (Using %10 creates an image that has both ordered and chaotic regions.)

Knight's Tour using Warnsdorff Algorithm (Python)

2012-12-17T06:04:19-08:00

Python recipe 578382 by FB36 (algorithm, algorithms, math, mathematics).

Knight's Tour using Warnsdorff Algorithm.

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.

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

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

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).

Binary Search Tree (C++)

2011-08-08T00:13:44-07:00

C++ recipe 577828 by sivarama sarma (algorithm, algorithms, datastructures).

Binary Search Tree.

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