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

## Extras

This is some additional code that is not automatically loaded by `using DiscreteFunctions`

.
Use `include`

on the appropriate file in the `src`

directory.

`src/tree_function.jl`

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 to the root, `1`

.

`src/draw_function.jl`

This file defines `draw(f)`

to give a picture of `f`

.