## 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.

36 people like this

**Posted**: 4 years ago by Tomas Petricek### Random 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.

53 people like this

**Posted**: 4 years ago by James### Array shuffle

Shuffle an array

46 people like this

**Posted**: 4 years ago by Laurent### Factorial

Calculates the factorial for positive integers

26 people like this

**Posted**: 4 years ago by Stefan Knoblauch### Composing 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".]

76 people like this

**Posted**: 4 years ago by Novox### Sequence Random Permutation

A generic function that randomly permutes the elements of a sequence.

43 people like this

**Posted**: 4 years ago by Taha Hachana### Project 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.

69 people like this

**Posted**: 4 years ago by Eugene Gavrin### Cartesian Product of Lists

Computes the Cartesian product of a list of lists. See also corresponding example for a sequence of sequences.

47 people like this

**Posted**: 4 years ago by Neil Carrier### Cartesian Product of Sequences

Computes the Cartesian product of a sequence of sequences. See corresponding example for a list of lists.

44 people like this

**Posted**: 4 years ago by Neil Carrier### Project 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.

35 people like this

**Posted**: 4 years ago by D### Fibonacci sequence

Cached fib sequence

12 people like this

**Posted**: 4 years ago by Dmitri Pavlenkov### Async hashing

Async memory or file hashing

10 people like this

**Posted**: 4 years ago by Mauricio Scheffer### Partition 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.

67 people like this

**Posted**: 4 years ago by Rick Minerich### Function 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.

44 people like this

**Posted**: 4 years ago by Tuomas Hietanen### Function 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**: 4 years ago by Ankur Dhama### Inline 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.

13 people like this

**Posted**: 4 years ago by Dmitri Pavlenkov### Project 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.

25 people like this

**Posted**: 4 years ago by Natallie Baikevich### Pascal's Triangle

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

18 people like this

**Posted**: 4 years ago by Dmitry Soshnikov### 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**: 4 years ago by Arjen Kopinga### Hex encode / decode

Performs conversions to and from hexadecimal values.

27 people like this

**Posted**: 4 years ago by Daniel Robinson### 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.

12 people like this

**Posted**: 4 years ago by Shamil Sayfutdinov### Cartesian 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**: 4 years ago by Alexander Rautenberg### 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.

19 people like this

**Posted**: 4 years ago by Horacio Nuñez### 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**: 4 years ago by Cesar Mendoza### Split 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.

72 people like this

**Posted**: 4 years ago by Dmitri Pavlenkov### MD5 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.

16 people like this

**Posted**: 4 years ago by Tim Robinson### Combinatorial 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**: 4 years ago by Cesar Mendoza### Powerset

Powerset of set represented as a list. Does not check for repeated elements

2 people like this

**Posted**: 4 years ago by Andrew Le Couteur Bisson### Factorial using Int64, Double and BigInteger

Recursive Factorial using Int64, Double and BigInteger with execution time.

1 people like this

**Posted**: 4 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**: 4 years ago by Carsten König### Permutations

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**: 4 years ago by Carsten König### Very 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:

8 people like this

**Posted**: 4 years ago by Rick Minerich### The 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.

2 people like this

**Posted**: 4 years ago by Nick Palladinos### Red-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**: 4 years ago by Carsten König### SHA512 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**: 4 years ago by Tuomas Hietanen### Weighted Quick-Union with Path Compression

Implementation of Mutable Weighted Quick-Union with Path Compression in F#

3 people like this

**Posted**: 4 years ago by Rick Minerich### All 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.

9 people like this

**Posted**: 4 years ago by Tomas Petricek### Permutation and Combination

Permutation and Combination using ListBuilder.

9 people like this

**Posted**: 3 years ago by zecl### 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**: 3 years ago by Matt Wilson### Seq.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**: 3 years ago by Tomas Petricek### Euler #5

Euler #5 solution

3 people like this

**Posted**: 3 years ago by Michael Falanga### RSK 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**: 3 years ago by Ademar Gonzalez### 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.

3 people like this

**Posted**: 3 years ago by Arjen Kopinga

### 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.

1 people like this

**Posted**: 3 years ago by Arjen Kopinga### Memoization 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.

3 people like this

**Posted**: 3 years ago by Tomas Petricek### Ninety-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.

4 people like this

**Posted**: 3 years ago by Cesar Mendoza### Ninety-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 years ago by Cesar Mendoza### Ninety-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.

4 people like this

**Posted**: 3 years ago by Cesar Mendoza### n-gram algorithm

Simple n-gram algorithm implementation <https://en.wikipedia.org/wiki/N-gram>

1 people like this

**Posted**: 3 years ago by Daniil Frumin### Turing 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**: 3 years ago by Daniil### Langton's ant

Implementation of Langton's ant route.. Takes first 1000 steps and returns only black fields.

1 people like this

**Posted**: 3 years ago by stejcz### Langton's ant // OOP :)

Implementation of Langton's ant route.. Takes first 1000 steps and returns only black fields.

3 people like this

**Posted**: 3 years ago by stejcz### A simple sieve

A simple implementation for the sieve of Eratosthenes.

3 people like this

**Posted**: 3 years ago by Gab_km### EditDistance

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

3 people like this

**Posted**: 3 years ago by Gustavo Guerra### Levenshtein distance

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

2 people like this

**Posted**: 3 years ago by Lakret### 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**: 3 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.

5 people like this

**Posted**: 3 years ago by Mathias Brandewinder### Yet 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**: 3 years ago by Tuomas Hietanen### fast Fourier transforms (FFT)

Naive "school-book" implimentation.

13 people like this

**Posted**: 2 years ago by Kaspar### Partition a list

The snippet implements 'List.partitionWhile' which behaves as a combination of 'Seq.takeWhile' and 'Seq.skipWhile': It splits the list into a part containing elements from the beginning of a list that match a given predicate and remaining elements.

5 people like this

**Posted**: 2 years ago by Tomas Petricek### 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.

2 people like this

**Posted**: 2 years ago by Joel Huang### QuickSort on List

Another version of QuickSort implementation.

2 people like this

**Posted**: 2 years ago by Joel Huang### Fibonacci snippet implement with Continuation

Normally, when we implement Fibonacci sequence, we use recursive function, but it will encounter the overflow exception with the big data. Below is the Fibonacci snippet with continuation, and in this way, it won't encounter the overflow exception.

5 people like this

**Posted**: 2 years ago by Jeallyn Duan### All 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.

0 people like this

**Posted**: 2 years ago by Tomas Petricek### All 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.

0 people like this

**Posted**: 2 years ago by Tomas Petricek### 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**: 2 years ago by isaiah perumalla### Factorial

Factorial versus tail recursion

3 people like this

**Posted**: 2 years ago by Laco### Fibonacci

fibonacci by Seq.Unfold

2 people like this

**Posted**: 2 years ago by Laco### Combinations n choose k

given an array n generates all lists with k choices from n

5 people like this

**Posted**: 2 years ago by isaiah perumalla### Yet another (combinatorial) way to compute the factorial

Compute the factorial of a given number by building the list of permutations of the list of first n numbers [1..n] and taking its length

2 people like this

**Posted**: 2 years ago by Dmitry Soshnikov### 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**: 2 years ago by devshorts### 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**: 2 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**: 1 years ago by Lakret### BST and DF Traversal

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

6 people like this

**Posted**: 1 years ago by Fabio Galuppo### Shuffle letters

Added recursive version

### Flips the bits (eg. 01000001 becomes 10000010)

better title

### factorial.fsx

Factorial recursive function using match with pattern.

0 people like this

**Posted**: 1 years ago by gg00xiv### factorial.fsx

Factorial recursive function using match ... with pattern.

0 people like this

**Posted**: 1 years ago by gg00xiv### Computing factorial using combinators

This snippet shows how to transform simple recursive factorial function to combinator form step-by-step.

2 people like this

**Posted**: 1 years ago by Dmitri Soshnikov### Array Shuffle

Shuffling array using Seq.fold

3 people like this

**Posted**: 1 years ago by Karlkim Suwanmongkol### List Multipartition

Needed to partition a list into multiple groups, but couldn't find an existing way to do it. Have not put this as an extension method as needed it in an .fsx file which is loaded, but couldn't get extension method to work from that.

1 people like this

**Posted**: 11 months ago by @BrockSamsonUK### 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**: 6 months ago by Antonio Prestes García### Parallel fold

Idea from Guy L. Steele - Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful - https://vimeo.com/6624203

5 people like this

**Posted**: 5 months ago by Tuomas Hietanen### ListShuffle

This simple snippet shuffles the elements of a list. It can be useful for simulations.

2 people like this

**Posted**: 5 months ago by Antonio Prestes García### Inverse Gamma function and Inverse Factorial by Approximation

Inverse Gamma function and Inverse Factorial by Approximation based on these references: http://mathforum.org/kb/message.jspa?messageID=342551&tstart=0 https://github.com/DarkoVeberic/LambertW

2 people like this

**Posted**: 11 days ago by Fabio Galuppo### Factorial with bigint and reduce

Factorial with bigint and reduce

2 people like this

**Posted**: 3 days ago by Andriy Tolstoy