1

0

0

1

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

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

01/20/2019