Tagged algorithms | F# Snippets

Snippets tagged algorithms

Pascal's Triangle

This code sample generates Pascal's triangle as jagged 2D list (list of lists).
19 people like this
Like the snippet!
Posted: 13 years ago by Dmitry Soshnikov
Pascal's Triangle (2)

This code sample generates Pascal's triangle as jagged 2D list (list of lists). It takes 0.5 sec to generate 3000 rows (vs 16 sec for http://fssnip.net/23). Tip: try to avoid of using "list1 @ list2" construction.
13 people like this
Like the snippet!
Posted: 13 years ago by Shamil Sayfutdinov
Primitive Pythagorean triples

Primitive Pythagorean triples generator. It uses an Algorithm found on Wolfram MathWorld and the F# PowerPack matrix library.
46 people like this
Like the snippet!
Posted: 13 years ago by Cesar Mendoza
A fast sieve of Eratosthenes

A prime Eratosthenes' sieve, using a bit array and sieving only odd composites to conserve memory and keep things fast.
4 people like this
Like the snippet!
Posted: 13 years ago by Arjen Kopinga
EditDistance

Computes the Minimum Edit Distance or the Levenshtein Distance between two words
3 people like this
Like the snippet!
Posted: 12 years ago by Gustavo Guerra
In-place parallel QuickSort

It's fairly straightforward in-place QuickSort implementation which uses ThreadPool for parallelization. Still slower than library function Array.sortInPlace, though.
3 people like this
Like the snippet!
Posted: 12 years ago by Lakret
fast Fourier transforms (FFT)

Naive "school-book" implimentation.
14 people like this
Like the snippet!
Posted: 12 years ago by Kaspar
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
8 people like this
Like the snippet!
Posted: 12 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
3 people like this
Like the snippet!
Posted: 11 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
Like the snippet!
Posted: 11 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.
3 people like this
Like the snippet!
Posted: 10 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
Like the snippet!
Posted: 9 years ago by Giacomo Stelluti Scala
QuickSort on List

Another version of QuickSort implementation.
6 people like this
Like the snippet!
Posted: 2 years ago by Shankar V

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
Like the snippet!
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
Like the snippet!
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
Like the snippet!
Posted: 13 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
Like the snippet!
Posted: 13 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
Like the snippet!
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
Like the snippet!
Posted: 12 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
Like the snippet!
Posted: 12 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
Like the snippet!
Posted: 12 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
Like the snippet!
Posted: 11 years ago by devshorts
BST and DF Traversal

Binary Search Tree and Depth-First Traversal (PreOrder, InOrder, PostOrder)
6 people like this
Like the snippet!
Posted: 11 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
Like the snippet!
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
Like the snippet!
Posted: 9 years ago by Sami Perttu
union find

This module implements a generic union-find data structure (from https://gist.github.com/vanaur/bea2b0ea57b58140b9c1d39a9b02e998).
7 people like this
Like the snippet!
Posted: 8 months ago by vanaur