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: 6 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: 6 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: 6 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: 6 years ago by Arjen Kopinga

  • Levenshtein distance

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

    6 people like this

    Posted: 5 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: 5 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.

    4 people like this

    Posted: 5 years ago by Joel Huang

  • Sequence of all Subsets of a set

    A function that returns a sequence of subsets generated by the power set of a specified set. The function use bit patterns to generate sets. for example the power set generated by a set with 3 elements set [1;2;3;] has 2^3 sets. each set in the power set is represented by the set bits in each of the integer from 0 to (2^3) -1

    6 people like this

    Posted: 5 years ago by isaiah perumalla

  • Binary search

    Simple binary search of an array. Tests the array at the middle and divides the search space by half each time it looks for the target item. Returns the target item and how many iterations it took to get there

    2 people like this

    Posted: 4 years ago by devshorts

  • Bron–Kerbosch maximal cliques algorithm

    Bron–Kerbosch algorithm is an algorithm for finding maximal cliques in an undirected graph http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

    1 people like this

    Posted: 4 years ago by Lakret

  • Fourth order Runge-Kutta ODE solver

    This is a simple and direct implementation of fourth order runge-kutta ordinary differential equation solver algorithm. In the main function three use cases are shown.

    1 people like this

    Posted: 2 years ago by Antonio Prestes García

  • String percentual similarity using Levenshtein Distance

    String percentual similarity using Levenshtein Distance, as described in https://en.wikipedia.org/wiki/Levenshtein_distance.

    0 people like this

    Posted: 2 years ago by Giacomo Stelluti Scala