Snippets tagged algorithms

• Pascal's Triangle

This code sample generates Pascal's triangle as jagged 2D list (list of lists).

19 people like this

Posted: 12 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

Posted: 12 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

Posted: 12 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

Posted: 11 years ago by Arjen Kopinga

• EditDistance

Computes the Minimum Edit Distance or the Levenshtein Distance between two words

3 people like this

Posted: 11 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

Posted: 10 years ago by Lakret

• fast Fourier transforms (FFT)

Naive "school-book" implimentation.

14 people like this

Posted: 10 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

Posted: 10 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

Posted: 9 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: 9 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

Posted: 8 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: 7 years ago by Giacomo Stelluti Scala

• QuickSort on List

Another version of QuickSort implementation.

5 people like this

Posted: 1 year 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

Posted: 12 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: 12 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: 11 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: 11 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: 10 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: 10 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: 10 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: 10 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: 9 years ago by devshorts

• BST and DF Traversal

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

6 people like this

Posted: 9 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: 8 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: 7 years ago by Sami Perttu