gleam_community_maths - v1.1.1

gleam_community/maths/combinatorics

Combinatorics: A module that offers mathematical functions related to counting, arrangements, and combinations.

Functions

cartesian_product

</> 
pub fn cartesian_product(
  xarr: List(a),
  yarr: List(a),
) -> List(#(a, a))

Generate a list containing all combinations of pairs of elements coming from two given lists.

Example: 
import gleeunit/should
import gleam/list
import gleam_community/maths/combinatorics

pub fn example () {
  []
  |> combinatorics.cartesian_product([])
  |> should.equal([])

  [1.0, 10.0]
  |> combinatorics.cartesian_product([1.0, 2.0])
  |> should.equal([#(1.0, 1.0), #(1.0, 2.0), #(10.0, 1.0), #(10.0, 2.0)])
}

combination

</> 
pub fn combination(n: Int, k: Int) -> Result(Int, String)

A combinatorial function for computing the number of a $$k$$-combinations of $$n$$ elements:

\[ C(n, k) = \binom{n}{k} = \frac{n!}{k! (n-k)!} \] Also known as “$$n$$ choose $$k$$” or the binomial coefficient.

The implementation uses the effecient iterative multiplicative formula for the computation.

Example: 
import gleeunit/should
import gleam_community/maths/combinatorics

pub fn example() {
  // Invalid input gives an error
  // Error on: n = -1 < 0
  combinatorics.combination(-1, 1)
  |> should.be_error()

  // Valid input returns a result
  combinatorics.combination(4, 0)
  |> should.equal(Ok(1))

  combinatorics.combination(4, 4)
  |> should.equal(Ok(1))

  combinatorics.combination(4, 2)
  |> should.equal(Ok(6))
}

factorial

</> 
pub fn factorial(n: Int) -> Result(Int, String)

A combinatorial function for computing the total number of combinations of $$n$$ elements, that is $$n!$$.

Example: 
import gleeunit/should
import gleam_community/maths/combinatorics

pub fn example() {
  // Invalid input gives an error
  combinatorics.factorial(-1)
  |> should.be_error()

  // Valid input returns a result
  combinatorics.factorial(0)
  |> should.equal(Ok(1))

  combinatorics.factorial(1)
  |> should.equal(Ok(1))

  combinatorics.factorial(2)
  |> should.equal(Ok(2))

  combinatorics.factorial(3)
  |> should.equal(Ok(6))

  combinatorics.factorial(4)
  |> should.equal(Ok(24))
}

list_combination

</> 
pub fn list_combination(
  arr: List(a),
  k: Int,
) -> Result(List(List(a)), String)

Generate all $$k$$-combinations based on a given list.

Example: 
import gleeunit/should
import gleam/set
import gleam_community/maths/combinatorics

pub fn example () {
  let assert Ok(result) = combinatorics.list_combination([1, 2, 3, 4], 3)
  result
  |> set.from_list()
  |> should.equal(set.from_list([[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]))
}

list_permutation

</> 
pub fn list_permutation(arr: List(a)) -> List(List(a))

Generate all permutations of a given list.

Repeated elements are treated as distinct for the purpose of permutations, so two identical elements for example will appear “both ways round”. This means lists with repeated elements return the same number of permutations as ones without.

N.B. The output of this function is a list of size factorial in the size of the input list. Caution is advised on input lists longer than ~11 elements, which may cause the VM to use unholy amounts of memory for the output.

Example: 
import gleeunit/should
import gleam/set
import gleam_community/maths/combinatorics

pub fn example () {
  [1, 2, 3]
  |> combinatorics.list_permutation()
  |> set.from_list()
  |> should.equal(set.from_list([
    [1, 2, 3],
    [2, 1, 3],
    [3, 1, 2],
    [1, 3, 2],
    [2, 3, 1],
    [3, 2, 1],
  ]))

  [1.0, 1.0]
  |> combinatorics.list_permutation()
  |> should.equal([[1.0, 1.0], [1.0, 1.0]])
}

permutation

</> 
pub fn permutation(n: Int, k: Int) -> Result(Int, String)

A combinatorial function for computing the number of $$k$$-permuations (without repetitions) of $$n$$ elements:

\[ P(n, k) = \frac{n!}{(n - k)!} \]

Example: 
import gleeunit/should
import gleam_community/maths/combinatorics

pub fn example() {
  // Invalid input gives an error
  // Error on: n = -1 < 0
  combinatorics.permutation(-1, 1)
  |> should.be_error()

  // Valid input returns a result
  combinatorics.permutation(4, 0)
  |> should.equal(Ok(1))

  combinatorics.permutation(4, 4)
  |> should.equal(Ok(1))

  combinatorics.permutation(4, 2)
  |> should.equal(Ok(12))
}
✨ Search Document