Snippets tagged algorithms

  • Anagrams

    Let's use the fundamental theorem of arithmetic to determine if two words are anagrams of each other. How? The theorem states (roughly) that each number can be written as a product of prime numbers in only one unique way. For instance 42 = 7 * 2 * 3 = 3 * 7 * 2. Now what will happen if you associate a letter with a unique prime number? You can see that "team" [71*11*2*41] = "meat" [41*11*2*71]. Oh, the possibilities. Note that in the code below big integers are used since the product of many primes will overflow a 32- or even a 64-bit integer.

    25 people like this

    Posted: 13 years ago by Arjen Kopinga

  • Pascal's Triangle

    Returns the pascal triangle in a 2D list . This snippet computes rows translating the 'visual' method taught at school into Lists and the usage of map2 function. It takes almost 5 seconds to compute 5000 rows.

    20 people like this

    Posted: 13 years ago by Horacio Nuñez

  • Soundex Algorithm

    Algorithms for generating US Census and Daitch-Mokotoff soundex string(s) based on a text input. Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling.

    4 people like this

    Posted: 12 years ago by Matt Wilson

  • Folding over prime factors

    Let's have some fun with higher order functions and instead of folding over a list, fold over the prime factors of a number. It can be optimized further by dividing out real primes instead of numbers of the form 6k+/-1, but it's not embarrassingly slow.

    2 people like this

    Posted: 12 years ago by Arjen Kopinga

  • Levenshtein distance

    Computes Levenshtein (min edit) distance between two strings http://en.wikipedia.org/wiki/Levenstein_Distance

    9 people like this

    Posted: 12 years ago by Lakret

  • Monotone Chain Convex Hull Algorithm

    Andrew's Monotone Chain Convex Hull algorithm: given points in 2 dimensions, determine their convex hull by constructing the upper and lower hull.

    6 people like this

    Posted: 11 years ago by Mathias Brandewinder

  • Merge Sort on List

    Merge Sort falls into 'Divide and Conquer' problem solving technique and it is a stable sorting. The worst case of running time is (nlogn). This implementation below follows the two abstract steps to achieve Merge Sort, i.e., * Recursively divide input list into two sub-lists. * Repeatedly merge the sub-lists.

    5 people like this

    Posted: 11 years ago by Joel Huang

  • Combinations n choose k

    given an array n generates all lists with k choices from n

    8 people like this

    Posted: 11 years ago by isaiah perumalla

  • Find largest mass in 2D array

    This is a modification of the flood fill algorithm to find the largest contiguous block of items in a 2D array. Also includes a simple flood fill finder given a canvas and the target point

    2 people like this

    Posted: 10 years ago by devshorts

  • BST and DF Traversal

    Binary Search Tree and Depth-First Traversal (PreOrder, InOrder, PostOrder)

    6 people like this

    Posted: 10 years ago by Fabio Galuppo

  • ListShuffle

    This simple snippet shuffles the elements of a list. It can be useful for simulations.

    4 people like this

    Posted: 9 years ago by Antonio Prestes García

  • Fun with Generic Bit Manipulation

    Some generic functions that use bit manipulation. They work for all signed integer types and are faster than the standard functions min, max, abs and sign.

    2 people like this

    Posted: 8 years ago by Sami Perttu