Snippets tagged Algorithms
Pascal's Triangle
This code sample generates Pascal's triangle as jagged 2D list (list of lists).
13 people like this
Posted: 1 years ago by Dmitry SoshnikovAnagrams
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.
15 people like this
Posted: 1 years ago by Arjen KopingaPascal'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.
8 people like this
Posted: 1 years ago by Shamil SayfutdinovPascal'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.
12 people like this
Posted: 1 years ago by Horacio NuñezPrimitive Pythagorean triples
Primitive Pythagorean triples generator. It uses an Algorithm found on Wolfram MathWorld and the F# PowerPack matrix library.
31 people like this
Posted: 1 years ago by Cesar MendozaSoundex 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: 9 months ago by Matt Wilson
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.
2 people like this
Posted: 6 months ago by Arjen KopingaFolding 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.
0 people like this
Posted: 6 months ago by Arjen KopingaEditDistance
Computes the Minimum Edit Distance or the Levenshtein Distance between two words
3 people like this
Posted: 2 months ago by Gustavo GuerraLevenshtein distance
Computes Levenshtein (min edit) distance between two strings http://en.wikipedia.org/wiki/Levenstein_Distance
1 people like this
Posted: 1 months ago by LakretIn-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: 1 months ago by LakretMonotone 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.
3 people like this
Posted: 1 months ago by Mathias Brandewinder