Sorting arrays of solutions

# Sorting arrays of solutions

We provide functions for sorting analyzing arrays of vectors.

## Computing unique points in an array of vectors

We provide the `unique_points` methods to sort through solutions.

``unique_points(points::AbstractVector{<:AbstractVector}; options...)``

Compute all unique points with respect to the given options. See `UniquePoints` for possible options. In particular, it is possible to pass group actions.

Example

``````julia> pts = [[1.0,0.5], [1.0,0.5], [0.5,1.0]];
julia> unique_points(pts)
2-element Array{Array{Float64,1},1}:
[1.0, 0.5]
[0.5, 1.0]

julia> unique_points(pts; group_action = x -> [x[2],x[1]])
1-element Array{Array{Float64,1},1}:
[1.0, 0.5]``````

The `unique_points` method is powered by the `UniquePoints` data structure.

``UniquePoints{V<:AbstractVector, T, F<:Function}``

A data structure which holds points of type `V` where `T=real(eltype(V))`. This data structure provides an efficient (poly)logarithmic check whether a point already exists where two points `u,v` are considered equal if `F(u,v)<tol`, where `tol` is a tolerance provided through the `add!` function.

``UniquePoints(v::AbstractVector{<:Number}, distance::F)``

Initialize the data structure with just one data point `v`.

``UniquePoints(V::Vector{<:AbstractVector{<:Number}}, distance::F; tol=1e-5)``

Initialize the data structure with all points in `v`. These are added in order by `add!` with the given tolerance `tol`. In particular, 'UniquePoints' structure will contain only points for which the pairwise distance given by `F` is less than `tol`.

``UniquePoints(v; kwargs...) = UniquePoints(v, euclidean_distance; kwargs...)``

If `F` is not specialized, `euclidean_distance` is used.

Optional keywords:

• `check_real=true` adds real from points from group orbits (if they exist). The default is `check_real=true`.
• The user can use `group_action=foo` or, if there is more than one group acting, `group_actions=[foo, bar]`. Then, points that are in the same group orbit are considered equal. See `GroupActions` for details regarding the application rules.

Examples

``````julia> points(UniquePoints([[1.0,0.5], [1.0,0.5], [0.5,1.0]]))
2-element Array{Array{Float64,1},1}:
[1.0, 0.5]
[0.5, 1.0]

julia> points(UniquePoints([[1.0,0.5], [1.0,0.5], [0.5,1.0]], group_action = x -> [x[2],x[1]]))
1-element Array{Array{Float64,1},1}:
[1.0, 0.5]``````

We provide several helper functions for `UniquePoints`.

``points(data::UniquePoints)``

Return the points stored in `data`.

``is_contained(data::UniquePoints{V}, x::V; tol=1e-5)::Bool``

Check whether `x` is contained in the `data` by using the tolerance `tol` to decide for duplicates.

``is_contained(data::UniquePoints{V}, x::V, Val{true}(); tol=1e-5)::Int``

If `x` is contained in `data` by using the tolerance `tol` return the index of the data point which already exists. If the data point is not existing `-1` is returned. If `data` has the option `check_real` enabled, a `-2` will be returned once a real vector was added.

``add!(data::UniquePoints{V}, x::V; tol=1e-5)::Bool``

Add `x` to `data` if it doesn't already exists by using the tolerance `tol` to decide for duplicates.

``add!(data::UniquePoints{V}, x::V, Val(true); tol=1e-5)::Int``

If `x` is contained in `data` by using the tolerance `tol` to decide for duplicates return the index of the data point which already exists. If the data point is not existing add it to `data` and return `-1`. If `data` has the option `check_real` enabled, a `-2` will be returned once a real vector was added. The element will be the last element of `points(data)`.

``simple_add!(data::UniquePoints{V}, x::V, tol::Real)::Bool``

Similarly to `add!` but does not apply any group actions. If the data point is not existing add it to `data` and return `-1`. Otherwise the index of `x` in `data.points` is returned.

``empty!(collection) -> collection``

Remove all elements from a `collection`.

Examples

``````julia> A = Dict("a" => 1, "b" => 2)
Dict{String,Int64} with 2 entries:
"b" => 2
"a" => 1

julia> empty!(A);

julia> A
Dict{String,Int64} with 0 entries``````
source
``empty!(data::UniquePoints)``

Remove all points from `data`.

## Computing points in an array of vectors which appear multiple times

If instead of unique points, the user wants to have the information which points in an array of points appear with multiplicity, they should use the next function.

``multiplicities(vectors; distance=euclidean_distance, tol::Real = 1e-5, kwargs...)``

Returns an array of arrays of integers. Each vector `w` in 'v' contains all indices `i,j` such that `w[i]` and `w[j]` have `distance` at most tol.

Optional keywords:

• `check_real=true` adds real from points from group orbits (if they exist) to the `UniquePoints` data structure used internally. The default is `check_real=false`.
• The user can use `group_action=foo` or, if there is more than one group acting, `group_actions=[foo, bar]`. Then, points that are in the same group orbit are considered equal. See `GroupActions` for details regarding the application rules.
``````julia> multiplicities([[1,0.5]; [1,0.5]; [1,1]])
[[1,2]]``````

This is the same as

``multiplicities([[1,0.5]; [1,0.5]; [1,1]]; distance=(x,y) -> LinearAlgebra.norm(x-y))``

Here is an example for using group actions.

``````julia> X = [[1, 2, 3, 4], [2,1,3,4], [1,2,4,3], [2,1,4,3]]
julia> permutation(x) = [x[2], x[1], x[3], x[4]]
julia> m = multiplicities(X, group_action = permutation)
[[1,2], [3,4]]``````
``multiplicities(V::Results; tol=1e-6)``

Returns a `Vector` of `Vector{PathResult}`s grouping the `PathResult`s whose solutions appear with multiplicities greater 1 in 'V'. Two solutions are regarded as equal, when their pairwise distance is less than 'tol'.

The `multiplicities` functions may also be applied to `Result`; see here: `multiplicities(::HomotopyContinuation.Results)`.