DiscreteFunctions

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

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.

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

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

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

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.

• 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).

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

This is some additional code that is not automatically loaded by using DiscreteFunctions. Use include on the appropriate file in the src directory.

This file defines tree2function(G::SimpleGraph). It assumes that G is a tree with vertex set 1:n and returns a DiscreteFunction defined by pointing all edges toward the root, 1.

This file defines draw(f) to give a picture of f.