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.

    30 people like this
    Posted: 3 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.

    46 people like this
    Posted: 3 years ago by James

  • Array shuffle

    Shuffle an array

    37 people like this
    Posted: 3 years ago by Laurent

  • Factorial

    Calculates the factorial for positive integers

    24 people like this
    Posted: 3 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".]

    71 people like this
    Posted: 3 years ago by Novox

  • Sequence Random Permutation

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

    39 people like this
    Posted: 3 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.

    62 people like this
    Posted: 3 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.

    45 people like this
    Posted: 3 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.

    42 people like this
    Posted: 3 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.

    32 people like this
    Posted: 3 years ago by D

  • Fibonacci sequence

    Cached fib sequence

    10 people like this
    Posted: 3 years ago by Dmitri Pavlenkov

  • Async hashing

    Async memory or file hashing

    9 people like this
    Posted: 3 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.

    57 people like this
    Posted: 3 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.

    40 people like this
    Posted: 3 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: 3 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.

    12 people like this
    Posted: 3 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.

    24 people like this
    Posted: 3 years ago by Natallie Baikevich

  • Pascal's Triangle

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

    17 people like this
    Posted: 3 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.

    22 people like this
    Posted: 3 years ago by Arjen Kopinga

  • Hex encode / decode

    Performs conversions to and from hexadecimal values.

    26 people like this
    Posted: 3 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.

    11 people like this
    Posted: 3 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: 3 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.

    17 people like this
    Posted: 3 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.

    45 people like this
    Posted: 3 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.

    69 people like this
    Posted: 3 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.

    15 people like this
    Posted: 3 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: 3 years ago by Cesar Mendoza

  • Powerset

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

    1 people like this
    Posted: 3 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: 3 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: 3 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: 3 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:

    6 people like this
    Posted: 3 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.

    1 people like this
    Posted: 3 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: 3 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: 3 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: 3 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: 3 years ago by Tomas Petricek

  • Permutation and Combination

    Permutation and Combination using ListBuilder.

    8 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: 2 years ago by Tomas Petricek

  • Euler #5

    Euler #5 solution

    3 people like this
    Posted: 2 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: 2 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: 2 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: 2 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: 2 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: 2 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: 2 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.

    3 people like this
    Posted: 2 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: 2 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: 2 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: 2 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: 2 years ago by stejcz

  • A simple sieve

    A simple implementation for the sieve of Eratosthenes.

    3 people like this
    Posted: 2 years ago by Gab_km

  • EditDistance

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

    3 people like this
    Posted: 2 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: 2 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: 2 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.

    4 people like this
    Posted: 2 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: 2 years ago by Tuomas Hietanen

  • fast Fourier transforms (FFT)

    Naive "school-book" implimentation.

    12 people like this
    Posted: 1 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: 1 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: 1 years ago by Joel Huang

  • QuickSort on List

    Another version of QuickSort implementation.

    2 people like this
    Posted: 1 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: 1 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: 1 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: 1 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: 1 years ago by isaiah perumalla

  • Factorial

    Factorial versus tail recursion

    3 people like this
    Posted: 1 years ago by Laco

  • Fibonacci

    fibonacci by Seq.Unfold

    2 people like this
    Posted: 1 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: 1 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: 1 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: 1 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: 1 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: 11 months ago by Lakret

  • BST and DF Traversal

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

    5 people like this
    Posted: 11 months ago by Fabio Galuppo

  • Shuffle letters

    Added recursive version

    0 people like this
    Posted: 11 months ago by

  • Flips the bits (eg. 01000001 becomes 10000010)

    better title

    0 people like this
    Posted: 10 months ago by

  • factorial.fsx

    Factorial recursive function using match with pattern.

    0 people like this
    Posted: 7 months ago by gg00xiv

  • factorial.fsx

    Factorial recursive function using match ... with pattern.

    0 people like this
    Posted: 7 months 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: 4 months ago by Dmitri Soshnikov

  • Array Shuffle

    Shuffling array using Seq.fold

    2 people like this
    Posted: 3 months 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.

    0 people like this
    Posted: 6 days ago by @BrockSamsonUK