DiscreteFunctions

This module defines the DiscreteFunction type which represents a function defined on the set {1,2,...,n} (n must be positive).

Basic Constructor

A DiscreteFunction is created by providing a list of values either by passing an array of Int values or as a list of Int arguments. For example, to define a function f with f(1)==2, f(2)==3, f(3)==1, and f(4)==4 we do this:

julia> using DiscreteFunctions

julia> f = DiscreteFunction([2,3,1,4]);

julia> g = DiscreteFunction(2,3,1,4);

julia> f==g
true

Function evaluation may use either f(x) or f[x]. It is possible to change the value of f at x using the latter.

Conversion of a `Permutation` to a `DiscreteFunction`

If p is a Permutation then DiscreteFunction(p) creates a DiscreteFunction based on p.

julia> using Permutations

julia> p = RandomPermutation(6)
(1,6)(2,5,3,4)

julia> DiscreteFunction(p)
DiscreteFunction on [6]
   1   2   3   4   5   6
   6   5   4   2   3   1

Conversely, if f is a DiscreteFunction that is invertible, it can be converted to a Permutation by Permutation(f).

Conversion of a `Matrix` to a `DiscreteFunction`

Let A be a square matrix with exactly one nonzero element in each row. Then DiscreteFunction(A) creates a DiscreteFunction f such that f[i]==j exactly when A[i,j] != 0.

This is the inverse of the Matrix function (see below). That is, if A==Matrix(f) then f==DiscreteFunction(A).

Special Constructors

IdentityFunction(n) creates the identity function on the set {1,2,...,n}.
RandomFunction(n) creates a random function on the set {1,2,...,n}.

Operations and Methods

The composition of functions f and g is computed with f*g. Exponentiation signals repeated composition, i.e., f^4 is the same as f*f*f*f.

We can test if f is invertible using has_inv(f) and inv(f) returns the inverse function (or throws an error if no inverse exists). This can also be computed as f^-1 and, in general, if f is invertible it can be raised to negative exponents. The function is_permutation is a synonym for has_inv.

Other methods

length(f) returns the number of elements in f's domain.
fixed_points(f) returns a list of the fixed points in the function.
cycles(f) returns a list of the cycles in the function.
image(f) returns a Set containing the output values of f.
sources(f) returns a list of all inputs to f that are not outputs of f.
Matrix(f) returns a square, zero-one matrix with a one in position i,j exactly when f(i)==j.
eigvals(f) returns the eigenvalues of Matrix(f).

Expensive operations

all_functions(n) returns an iterator for all functions defined on 1:n. Note that there are n^n such functions so this grows quickly.
sqrt(g) returns a DiscreteFunction f such that f*f==g or throws an error if no such function exists. Found using integer linear programming.
all_sqrts(g) returns a list of all square roots of g. Very slow.