Snippets in category Algorithms
Random walk
Create sequence of floating point values generated by random walk process. Functional solution using sequence expressions and yield! construct in a tail-call position.
22 people like this
Posted: 1 years ago by Tomas PetricekRandom Walk
Random walk on integers starting at zero. At each step, we either add or subtract one depending on a random coin flip. The code uses Seq.unfold to generate infinite sequence.
28 people like this
Posted: 1 years ago by JamesArray shuffle
Shuffle an array
27 people like this
Posted: 1 years ago by LaurentFactorial
Calculates the factorial for positive integers
21 people like this
Posted: 1 years ago by Stefan KnoblauchComposing a list of functions
Composition of functions in F# is easily achieved by using the >> operator. You can also chain an arbitary amount of functions (represented as a list or sequence) together by folding the list/seq with >>. [More formally: the set of endomorphisms 'a -> 'a forms a monoid with the binary, associative operator ">>" (or "<<") and the neutral element "id".]
59 people like this
Posted: 1 years ago by NovoxSequence Random Permutation
A generic function that randomly permutes the elements of a sequence.
29 people like this
Posted: 1 years ago by Taha HachanaProject Euler #1
This snippet is code that solves first Project Euler problem. It finds the sum of all the multiples of 3 or 5 below 1000. Please add other (more efficient, succinct or interesting) solutions to this snippet.
37 people like this
Posted: 1 years ago by Eugene GavrinCartesian Product of Lists
Computes the Cartesian product of a list of lists. See also corresponding example for a sequence of sequences.
34 people like this
Posted: 1 years ago by Neil CarrierCartesian Product of Sequences
Computes the Cartesian product of a sequence of sequences. See corresponding example for a list of lists.
31 people like this
Posted: 1 years ago by Neil CarrierProject Euler #2
Solution to Project Euler problem 2: Find sum of even terms in fibonacci sequence which do not exceed four million. Comments about the first version: 1. It does't use memoize becouse of recursive call to unmemoized function "fibs". So it take over 20 sec to get answer. A minor change ("fibs" to "fibs' ") reduces this time to 140ms.
25 people like this
Posted: 1 years ago by DFibonacci sequence
Cached fib sequence
10 people like this
Posted: 1 years ago by Dmitri PavlenkovAsync hashing
Async memory or file hashing
8 people like this
Posted: 1 years ago by Mauricio SchefferPartition a sequence until a predicate is satiated
This function is given a partition predicate and a sequence. Until the predicate returns false, a list will be filled with elements. When it is, both the list and the remainder of the sequence will be returned. Note that this example preserves the laziness of the unchecked sequence elements.
38 people like this
Posted: 1 years ago by Rick MinerichFunction to get all possible combinations
Function to get all possible combinations of list items. There are some Euler problems (like 77 & 78) to get total amounts. But e.g. for some card game implementations you will need the real items.
27 people like this
Posted: 1 years ago by Tuomas HietanenFunction to generate all possible combinations where combination "ab" != "ba"
Function to generate all possible combinations where combination "ab" is different then "ba"
5 people like this
Posted: 1 years ago by Ankur DhamaInline factorial samples with fix point
While reading Tomas Petricek's master thesis, came across FIX operator implementation. Decided to experiment with various implementations of factorial.
10 people like this
Posted: 1 years ago by Dmitri PavlenkovProject Euler #182
The RSA encryption is based on the following procedure: Generate two distinct primes p and q. Compute n=pq and phi=(p-1)(q-1). Find an integer e, 1<e<phi, such that gcd(e,phi)=1. There exist values of e and m such that m^(e) mod n=m. We call messages m for which m^(e) mod n=m unconcealed messages. Choose p=1009 and q=3643. Find the sum of all values of e, so that the number of unconcealed messages for this value of e is at a minimum.
20 people like this
Posted: 1 years ago by Natallie BaikevichPascal'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 KopingaHex encode / decode
Performs conversions to and from hexadecimal values.
20 people like this
Posted: 1 years ago by Daniel RobinsonPascal'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 SayfutdinovCartesian product of n lists
Cartesian product of a variable number of lists. Input is a list of lists of which the cartesian product is to be constructed; output is a list that contains the elements of the product set, as lists.
11 people like this
Posted: 1 years ago by Alexander RautenbergPascal'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 MendozaSplit a list
Three ways to split a list in half (but not necessarily in the middle). A forth version added that's very short and should be fast, as we only use List.fold. New champ found.
48 people like this
Posted: 1 years ago by Dmitri PavlenkovMD5 hash
A function that computes an MD5 hash from a block of bytes. MD5 isn't cryptographically secure, but it's a handy way of condensing a block of data into a short string.
14 people like this
Posted: 1 years ago by Tim RobinsonCombinatorial functions
Here is my F# take on some combinatorial functions from the book "Introduction to Functional Programming" by Richard Bird and Philip Wadler.
5 people like this
Posted: 1 years ago by Cesar MendozaPowerset
Powerset of set represented as a list. Does not check for repeated elements
1 people like this
Posted: 1 years ago by Andrew Le Couteur BissonFactorial using Int64, Double and BigInteger
Recursive Factorial using Int64, Double and BigInteger with execution time.
0 people like this
Posted: 1 years ago by Carlos Quintanilla
Fun with polynoms and inline
for all those wanting to see the (rather unknown) statical interference of type-parameters (in contrast to generic type parameters) in action. I demonstrated this by having som e fun with basic algebra and polynoms
0 people like this
Posted: 1 years ago by Carsten KönigPermutations
computes the list of all permutations of a list for example the permutations of [1;2;3] will be [1;2;3]; [1;3;2]; [2;1;3]; [2;3;1]; [3;1;2]; [3;2;1]
2 people like this
Posted: 1 years ago by Carsten KönigVery Fast Permutations
I spent a lot of time this week profiling different permutation functions from various places on the internet. The following was by far the fastest:
4 people like this
Posted: 1 years ago by Rick MinerichThe repmin problem
The repmin problem is to replace all elements of a tree of numbers by the minimum element, making only a single pass over the original tree. Repmin is a very ingenious example of Circular Programming.
1 people like this
Posted: 1 years ago by Nick PalladinosRed-Black-Trees with insert
Found an very good article on RS-Trees in Haskell (see: http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps) It heavyly uses pattern recognition to translate those pesky balance-rules into short code. Bellowe is the simple rewrite of the haskell-implementation in F# - enjoy
4 people like this
Posted: 1 years ago by Carsten KönigSHA512 hash code from a string
Generates SHA512 hash code from a string. Usually used in some kind of validity checks, e.g. check first timestamp and then check SHA-hash over id and timestamp to ensure a valid session.
2 people like this
Posted: 1 years ago by Tuomas HietanenWeighted Quick-Union with Path Compression
Implementation of Mutable Weighted Quick-Union with Path Compression in F#
2 people like this
Posted: 11 months ago by Rick MinerichAll subsets of a set
A function implemented using sequence expressions that returns all subsets of a specified set. The function is not optimized, but it is very easy to understand.
8 people like this
Posted: 11 months ago by Tomas PetricekPermutation and Combination
Permutation and Combination using ListBuilder.
8 people like this
Posted: 9 months ago by zeclSoundex 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 WilsonSeq.reduceBallanced function
The function has the same type as Seq.reduce. Instead of reducing elements from the left to the right, it splits the input into two halves, reduces each half separately and then aggregates the results using the given function. This means that the values are aggregated into a ballanced tree, which can save stack space.
2 people like this
Posted: 9 months ago by Tomas PetricekEuler #5
Euler #5 solution
3 people like this
Posted: 8 months ago by Michael FalangaRSK algorithm
Implements a bijective mapping between permutations and pairs of standard Young tableaux, both having the same shape. http://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence
4 people like this
Posted: 7 months ago by Ademar GonzalezA 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 KopingaMemoization for dynamic programming
The snippet shows how to implement reusable memoization function and how to use it to implement efficient Fibonacci number generator using dynamic programming.
1 people like this
Posted: 6 months ago by Tomas PetricekNinety-Nine F# Problems - Problems 54 - 60 - Binary trees
These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.
2 people like this
Posted: 3 months ago by Cesar MendozaNinety-Nine F# Problems - Problems 61 - 69 - Binary trees
These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.
2 people like this
Posted: 3 months ago by Cesar MendozaNinety-Nine F# Problems - Problems 70 - 73 - Multiway Trees
These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.
3 people like this
Posted: 3 months ago by Cesar Mendozan-gram algorithm
Simple n-gram algorithm implementation <https://en.wikipedia.org/wiki/N-gram>
1 people like this
Posted: 2 months ago by Daniil FruminTuring machine interpreter
A Turing machine emulator. An infinite tape is simulated by a zipper, instructions are stored in the binary tree for faster lookup.
3 people like this
Posted: 2 months ago by DaniilLangton's ant
Implementation of Langton's ant route.. Takes first 1000 steps and returns only black fields.
1 people like this
Posted: 2 months ago by stejczLangton's ant // OOP :)
Implementation of Langton's ant route.. Takes first 1000 steps and returns only black fields.
3 people like this
Posted: 2 months ago by stejczA simple sieve
A simple implementation for the sieve of Eratosthenes.
3 people like this
Posted: 2 months ago by Gab_kmEditDistance
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 BrandewinderYet another Fibonacci
In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence: [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; ...] http://en.wikipedia.org/wiki/Fibonacci_number
4 people like this
Posted: 11 days ago by Tuomas Hietanen