tryalgo package#

Submodules#

tryalgo.PC_tree module#

Rami Benelmir, Christoph Dürr, Erisa Kohansal - 2023

The PC-tree is a dynamic data-structure which encodes permutations on the integers modulo n satisfying constraints of the form: - for a given set S the permutations need to keep the elements of S in consecutive order. Here we consider a circular order, i.e. after n-1 comes 0, then 1 and so on.

TODO: - annotations de type

class tryalgo.PC_tree.C_node(neighbors: List[Node] = [])[source]#

Bases: Node

clean()[source]#: Reset the attributes to their default values.

detach(old)[source]#: Removes a neighbor.

flip()[source]#: Inverts the order of the neighbors.

frontier(trace: List[int], enter: Node)[source]#: Exploring the the tree and writing the leafs in the order they are discovered. enter is the neighbor of the current node from which the tree exploration was initiated

represent(show_parent=False)[source]#: Returns a list representation of the node. Used for showing the C node correctly in the terminal and for unit-tests.

signal_full(fullNeighbor)[source]#: Receive the signal and update the counter of full elements and adds the received element to the full nodes.

split()[source]#: Splits a C node. Returns a new C-node with all full neighbors.

to_signal()[source]#: Determines which neighbor is the only non full neighbor.

exception tryalgo.PC_tree.Infeasible(reason)[source]#

Bases: Exception

Exception raised if the restriction is impossible for some reason.

class tryalgo.PC_tree.Leaf(ID)[source]#

Bases: Node

attach(new)[source]#: Defines a new parent for the element.

clean()[source]#: Reset the attributes to their default values.

detach(old)[source]#: Removes the link between an element and the parent.

frontier(trace: List[int], enter: Node)[source]#: Exploring the the tree and writing the leafs in the order they are discovered. enter is the neighbor of the current node from which the tree exploration was initiated

is_full()[source]#: Check if the element is full. Return True or False.

to_signal()[source]#: Leaf signal to the parent that they are full.

class tryalgo.PC_tree.Node(ID=None)[source]#

Bases: ABC

This class is to group attributes and methods common to the subclasses. But it is not intended to be instantiated. Hence the heritage from ABC (Abstract Base Class).

attach(new)[source]#: Adds the new element to the neighbors.

attach_neighbors() → None[source]#: Used only during the initialization of C_node and P_node. Manages the links between neighbors and parent

clean()[source]#: Reset the attributes to their default values.

detach(old)[source]#: Removes a neighbor.

detach_bilateral(to_detach)[source]#: Deletes the link between this node and all given neighbors

is_full() → bool[source]#: Check if the element is full. Return True or False.

is_partial()[source]#: Check if the element is full. Return True or False.

represent_parent(show_parent: bool) → List[int | None][source]#: Returns a list (empty or singleton) representing the parent of the node.

signal_full()[source]#: Receive the signal and update the counter of full elements.

class tryalgo.PC_tree.PC_tree(nb_leaves: int)[source]#

Bases: object

frontier() → List[int][source]#: Returns a permutation on {0, 1, …, n-1} satisfying all given restrictions.

print_dot()[source]#: Prints the PC-tree in dot format. Redirect the output in a file t.dot, which can be rendered for example with dot t.dot -T pdf -o t.pdf

represent(show_parent=False)[source]#: Printing the PC tree in the terminal.

restrict(restriction)[source]#: Refines the PC tree with the restrictions passed in the arguments.

class tryalgo.PC_tree.P_node(neighbors: Set[Node] = {})[source]#

Bases: Node

clean()[source]#: Reset the attributes to their default values.

frontier(trace: List[int], enter: Node)[source]#: Exploring the the tree and writing the leafs in the order they are discovered. enter is the neighbor of the current node from which the tree exploration was initiated

represent(show_parent=False)[source]#: Prints the C node in the terminal.

signal_full(full_neighbor)[source]#: Receive the signal and update the counter of full elements and adds the fullNeighbor to its full set.

split()[source]#: Create a new full node that contains all the full neighbors of this element, and it becomes an empty node.

to_signal()[source]#: Determines and returns the only non full element for a full node.

tryalgo.Sequence module#

Sequence.py

Doubly-linked circular list for maintaining a sequence of items subject to insertions and deletions.

Modified by Rami Benelmir, Christoph Dürr, Erisa Kohansal - 2023

we adapted the data structure to store only objects and to permit to replace objects easily. we changed the name of the function “append” to “add” for simplifying our code.

class tryalgo.Sequence.Sequence(iterable=[], key=<built-in function id>)[source]#

Bases: object

Maintain a sequence of items subject to insertions and removals. All sequence operations take constant time except indexing, which takes time proportional to the index.

add(x)[source]#: Add x to the end of the sequence.

insertAfter(x, y)[source]#: Add y after x in the sequence.

insertBefore(x, y)[source]#: Add y before x in the sequence.

key(x)[source]#: Apply supplied key function.

predecessor(x)[source]#: Find the previous element in the sequence.

remove(x)[source]#: Remove x from the sequence.

replace(old, new)[source]#: Replace an object by another one, preserving the position in the sequence

successor(x)[source]#: Find the next element in the sequence.

exception tryalgo.Sequence.SequenceError[source]#: Bases: Exception

tryalgo.a_star module#

Shortest Path algorithm A*.

jill-jênn vie et christoph dürr - 2023

tryalgo.a_star.a_star(graph, start, lower_bound)[source]#

single source shortest path by A* on an unweighted graph

Parameters:

graph – iterator on adjacent vertices
source – source vertex
lower_bound – lb function on distance to target, must return 0 on target and only there.

Returns:

distance or -1 (target unreachable)

Complexity:

O(|V| + |E|log|V|)

tryalgo.anagrams module#

Anagrams christoph dürr - jill-jênn vie - 2013-2019

tryalgo.anagrams.anagrams(S)[source]#

group a set of words into anagrams

Parameters:: S – set of strings
Returns:: list of lists of strings
Complexity:: $O(n k log k)$ in average, for n words of length at most k. $O(n^2 k log k)$ in worst case due to the usage of a dictionary.

tryalgo.arithm module#

arithmetic functions

christoph dürr - jill-jênn vie - 2013-2019

tryalgo.arithm.bezout(a, b)[source]#

Bézout coefficients for a and b

Parameters:: a,b – non-negative integers
Complexity:: O(log a + log b)

tryalgo.arithm.binom(n, k)[source]#

Binomial coefficients for $n choose k$

Parameters:: n,k – non-negative integers
Complexity:: O(k)

tryalgo.arithm.binom_modulo(n, k, p)[source]#

Binomial coefficients for $n choose k$, modulo p

Parameters:: n,k – non-negative integers
Complexity:: O(k)

tryalgo.arithm.inv(a, p)[source]#

Inverse of a in ${mathbb Z}_p$

Parameters:: a,p – non-negative integers
Complexity:: O(log a + log p)

tryalgo.arithm.pgcd(a, b)[source]#

Greatest common divisor for a and b

Parameters:: a,b – non-negative integers
Complexity:: O(log a + log b)

tryalgo.arithm_expr_eval module#

Evaluate an arithmetic expression

jill-jenn vie et christoph durr - 2014-2020

tryalgo.arithm_expr_eval.arithm_expr_eval(cell, expr)[source]#

Evaluates a given expression

Parameters:

expr – expression
cell – dictionary variable name -> expression

Returns:

numerical value of expression

Complexity:

linear

tryalgo.arithm_expr_eval.arithm_expr_parse(line_tokens)[source]#

Constructs an arithmetic expression tree

Parameters:: line_tokens – list of token strings containing the expression
Returns:: expression tree
Complexity:: linear

tryalgo.arithm_expr_target module#

Create arithmetic expression approaching target value

jill-jênn vie, christoph dürr et jean-christophe filliâtre - 2014-2019

tryalgo.arithm_expr_target.arithm_expr_target(x, target)[source]#

Create arithmetic expression approaching target value

Parameters:

x – allowed constants
target – target value

Returns:

string in form ‘expression=value’

Complexity:

huge

tryalgo.bellman_ford module#

Single source shortest paths by Bellman-Ford

jill-jenn vie et christoph durr - 2014-2018

tryalgo.bellman_ford.bellman_ford(graph, weight, source=0)[source]#

Single source shortest paths by Bellman-Ford

Parameters:

graph – directed graph in listlist or listdict format
weight – can be negative. in matrix format or same listdict graph

Returns:

distance table, precedence table, bool

Explanation:

bool is True if a negative circuit is reachable from the source, circuits can have length 2.

Complexity:

O(|V|*|E|)

tryalgo.bellman_ford.bellman_ford2(graph, weight, source)[source]#

Single source shortest paths by Bellman-Ford

Parameters:

graph – directed graph in listlist or listdict format
weight – can be negative. in matrix format or same listdict graph

Returns:

distance table, precedence table, bool

Explanation:

bool is true if there is a negative cycle reachable from the source. distance[v] is +inf if vertex v is not reachable from source and -inf if there are paths from the source to v of arbitrary small weight.

Complexity:

O(|V|*|E|)

tryalgo.bfs module#

Breadth-first search (bfs)

christoph dürr - jill-jênn vie - 2015-2019, 2023

tryalgo.bfs.bfs(graph, start=0)[source]#

Shortest path in unweighted graph by BFS

Parameters:

graph – directed graph in listlist or listdict format
start (int) – source vertex

Returns:

distance table, precedence table

Complexity:

O(|V|+|E|)

tryalgo.bfs.bfs_implicit(graph, start, end)[source]#

Shortest path by BFS in an implicitly directed graph

Parameters:

graph – function mapping a given vertex to an iterator over the neighboring vertices
start – source vertex
end – target vertex

Returns:

list of vertices of a shortest path or None

Complexity:

O(|V|+|E|)

tryalgo.biconnected_components module#

bi-connected components, cut vertices and cut cut-nodes

jill-jenn vie, christoph durr et louis abraham - 2015-2019

tryalgo.biconnected_components.cut_nodes_edges(graph)[source]#

Bi-connected components

Parameters:: graph – undirected graph. in listlist format. Cannot be in listdict format.
Returns:: a tuple with the list of cut-nodes and the list of cut-edges
Complexity:: O(|V|+|E|)

tryalgo.biconnected_components.cut_nodes_edges2(graph)[source]#

Bi-connected components, alternative recursive implementation

Parameters:: graph – undirected graph. in listlist format. Cannot be in listdict format.
Assumes:: graph has about 5000 vertices at most, otherwise memory limit is reached
Returns:: a tuple with the list of cut-nodes and the list of cut-edges
Complexity:: O(|V|+|E|) in average, O(|V|+|E|^2) in worst case due to use of dictionary

tryalgo.binary_search module#

Binary search

jill-jênn vie, christoph dürr et louis abraham - 2014-2020

tryalgo.binary_search.continuous_binary_search(f, lo, hi, gap=0.0001)[source]#

Binary search for a function

Parameters:

f – boolean monotone function with f(hi) = True
lo (int) –
hi (int) – with hi >= lo
gap (float) –

Returns:

first value x in [lo,hi] such that f(x), x is computed up to some precision

Complexity:

O(log((hi-lo)/gap))

tryalgo.binary_search.discrete_binary_search(tab, lo, hi)[source]#

Binary search in a table

Parameters:

tab – boolean monotone table with tab[hi] = True
lo (int) –
hi (int) – with hi >= lo

Returns:

first index i in [lo,hi] such that tab[i]

Complexity:

O(log(hi-lo))

tryalgo.binary_search.optimized_binary_search(tab, logsize)[source]#

Binary search in a table using bit operations

Parameters:

tab – boolean monotone table of size $2^\textrm{logsize}$ with tab[hi] = True
logsize (int) –

Returns:

first i such that tab[i]

Complexity:

O(logsize)

tryalgo.binary_search.optimized_binary_search_lower(tab, logsize)[source]#

Binary search in a table using bit operations

Parameters:

tab – boolean monotone table of size $2^\textrm{logsize}$ with tab[0] = False
logsize (int) –

Returns:

last i such that not tab[i]

Complexity:

O(logsize)

tryalgo.binary_search.ternary_search(f, lo, hi, gap=1e-10)[source]#

Ternary maximum search for a bitonic function

Parameters:

f – boolean bitonic function (increasing then decreasing, not necessarily strictly)
lo (int) –
hi (int) – with hi >= lo
gap (float) –

Returns:

value x in [lo,hi] maximizing f(x), x is computed up to some precision

Complexity:

O(log((hi-lo)/gap))

tryalgo.bipartite_matching module#

Bipartie maximum matching

jill-jenn vie et christoph durr - 2014-2018

tryalgo.bipartite_matching.max_bipartite_matching(bigraph)[source]#

Bipartie maximum matching

Parameters:: bigraph – adjacency list, index = vertex in U, value = neighbor list in V
Comment:: U and V can have different cardinalities
Returns:: matching list, match[v] == u iff (u, v) in matching
Complexity:: O(|V|*|E|)

tryalgo.bipartite_vertex_cover module#

Bipartie vertex cover

jill-jenn vie et christoph durr - 2014-2018

tryalgo.bipartite_vertex_cover.bipartite_vertex_cover(bigraph)[source]#

Bipartite minimum vertex cover by Koenig’s theorem

Parameters:: bigraph – adjacency list, index = vertex in U, value = neighbor list in V
Assumption:: U = V = {0, 1, 2, …, n - 1} for n = len(bigraph)
Returns:: boolean table for U, boolean table for V
Comment:: selected vertices form a minimum vertex cover, i.e. every edge is adjacent to at least one selected vertex and number of selected vertices is minimum
Complexity:: O(|V|*|E|)

tryalgo.closest_points module#

Closest pair of points trouver la paire de points la plus proche

jill-jênn vie, christoph dürr et louis abraham - 2014-2019

tryalgo.closest_points.closest_points(S)[source]#

Closest pair of points

Parameters:: S – list of points
Requires:: size of S at least 2
Modifies:: changes the order in S
Returns:: pair of points p,q from S with minimum Euclidean distance
Complexity:: expected linear time

tryalgo.closest_values module#

Closest values

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.closest_values.closest_values(L)[source]#

Closest values

Parameters:: L – list of values
Returns:: two values from L with minimal distance
Modifies:: the order of L
Complexity:: O(n log n), for n=len(L)

tryalgo.convex_hull module#

Convex hull by Andrew

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.convex_hull.andrew(S)[source]#

Convex hull by Andrew

Parameters:: S – list of points as coordinate pairs
Requires:: S has at least 2 points
Returns:: list of points of the convex hull
Complexity:: O(n log n)

tryalgo.dancing_links module#

Exact set cover by the dancing links algorithm

jill-jenn vie et christoph durr - 2014-2018

tryalgo.dancing_links.dancing_links(size_universe, sets)[source]#

Exact set cover by the dancing links algorithm

Parameters:

size_universe – universe = {0, 1, …, size_universe - 1}
sets – list of sets

Returns:

list of set indices partitioning the universe, or None

Complexity:

huge

tryalgo.dfs module#

Depth-first search - DFS

jill-jênn vie et christoph durr - 2015-2019

tryalgo.dfs.dfs_grid(grid, i, j, mark='X', free: str = '.') → None[source]#

DFS on a grid, mark connected component, iterative version

Parameters:

grid – matrix, 4-neighborhood
i,j – cell in this matrix, start of DFS exploration
free – symbol for walkable cells
mark – symbol to overwrite visited vertices

Complexity:

linear

tryalgo.dfs.dfs_grid_recursive(grid: List[List[str]], i: int, j: int, mark: str = 'X', free: str = '.') → None[source]#

DFS on a grid, mark connected component, recursive version

Parameters:

grid – matrix, 4-neighborhood
i,j – cell in this matrix, start of DFS exploration
free – symbol for walkable cells
mark – symbol to overwrite visited vertices

Complexity:

linear

tryalgo.dfs.dfs_iterative(graph: List[List[int]] | List[Dict[int, Any]] | GraphNamedVertices, start: int, seen: List[bool]) → None[source]#

DFS, detect connected component, iterative implementation

Parameters:

graph – directed graph in listlist or listdict format
node (int) – to start graph exploration
seen (boolean-table) – will be set true for the connected component containing node.

Complexity:

O(|V|+|E|)

tryalgo.dfs.dfs_recursive(graph: List[List[int]] | List[Dict[int, Any]] | GraphNamedVertices, node: int, seen: List[bool]) → None[source]#

DFS, detect connected component, recursive implementation

Parameters:

graph – directed graph in listlist or listdict format
node (int) – to start graph exploration
seen (boolean-table) – will be set true for the connected component containing node.

Complexity:

O(|V|+|E|)

tryalgo.dfs.dfs_tree(graph: List[List[int]] | List[Dict[int, Any]] | GraphNamedVertices, start: int = 0) → List[int | None][source]#

DFS, build DFS tree in unweighted graph

Parameters:

graph – directed graph in listlist or listdict format
start (int) – source vertex

Returns:

precedence table

Complexity:

O(|V|+|E|)

tryalgo.dfs.find_cycle(graph: List[List[int]] | List[Dict[int, Any]] | GraphNamedVertices) → List[int] | None[source]#

find a cycle in an undirected graph

Parameters:: graph – undirected graph in listlist or listdict format
Returns:: list of vertices in a cycle or None
Complexity:: O(|V|+|E|)

tryalgo.dfs.is_bipartite(G: List[List[int]] | List[Dict[int, Any]] | GraphNamedVertices) → bool[source]#

Checks whether a given graph is bipartite.

This is done by a graph traversal, assigning alternating colors. Once an edge with identicial endpoint colors is detected we know graph is not bipartite.

Parameters:: G – graph
Returns:: True if G is bipartite
Complexity:: linear

tryalgo.dijkstra module#

Shortest paths by Dijkstra

jill-jênn vie et christoph dürr - 2015-2018

tryalgo.dijkstra.dijkstra(graph, weight, source=0, target=None)[source]#

single source shortest paths by Dijkstra

Parameters:

graph – directed graph in listlist or listdict format
weight – in matrix format or same listdict graph
source (int) – source vertex
target (int) – if given, stops once distance to target found

Assumes:

weights are non-negative

Returns:

distance table, precedence table

Complexity:

O(|V| + |E|log|V|)

tryalgo.dijkstra.dijkstra_update_heap(graph, weight, source=0, target=None)[source]#

single source shortest paths by Dijkstra with a heap implementing item updates

Parameters:

graph – adjacency list or adjacency dictionary of a directed graph
weight – matrix or adjacency dictionary
source (int) – source vertex
target (int) – if given, stops once distance to target found

Assumes:

weights are non-negatif and weights are infinite for non edges

Returns:

distance table, precedence table

Complexity:

O(|V| + |E|log|V|)

tryalgo.dilworth module#

Decompose DAG into a minimum number of chains

jill-jenn vie et christoph durr - 2015-2018

tryalgo.dilworth.dilworth(graph)[source]#

Decompose a DAG into a minimum number of chains by Dilworth

Parameters:: graph – directed graph in listlist or listdict format
Assumes:: graph is acyclic
Returns:: table giving for each vertex the number of its chains
Complexity:: same as matching

tryalgo.dinic module#

Maximum flow by Dinic

jill-jênn vie et christoph dürr - 2015-2018

tryalgo.dinic.dinic(graph, capacity, source, target)[source]#

Maximum flow by Dinic

Parameters:

graph – directed graph in listlist or listdict format
capacity – in matrix format or same listdict graph
source (int) – vertex
target (int) – vertex

Returns:

skew symmetric flow matrix, flow value

Complexity:

$O(|V|^2 |E|)$

tryalgo.dist_grid module#

Distances in a grid

jill-jenn vie et christoph durr - 2014-2018

tryalgo.dist_grid.dist_grid(grid, source, target=None)[source]#

Distances in a grid by BFS

Parameters:

grid – matrix with 4-neighborhood
source ((int,int)) – pair of row, column ind_ices
target ((int,int)) – exploration stops if target is reached

Complexity:

linear in grid size

tryalgo.dyn_prog_tricks module#

Dynamic Programming speedup tricks

christoph dürr - jill-jênn vie - 2022

tryalgo.dyn_prog_tricks.decode_root_matrix_to_level(R)[source]#: Decodes a binary search tree encoded in the root matrix R into a level array :returns: the level array :complexity: linear

tryalgo.dyn_prog_tricks.dyn_prog_Monge(W)[source]#

Solves the following dynamic program for 0 <= i < j < n

C[i,i] = 0 C[i,j] = W[i,j] + min over i < k <= j of (C[i,k-1] + C[k,j]) K[i,j] = minimizer of above

Parameters:: W – matrix of dimension n times n
Assumes:: W satisfies the Monge property (a.k.a. quadrangle inequality) and monotonicity in the lattice of intervals
Returns:: C[0,n-1] and the matrix K with the minimizers
Complexity:: O(n^2)

tryalgo.dyn_prog_tricks.opt_bin_search_tree1(freq)[source]#

Optimal binary search tree on elements from 0 to n-1

Parameters:: freq – n dimensional array with frequency of every element i.
Returns:: The value of an optimal search tree and the matrix with the roots for each subproblem, encoding the actual tree.
Complexity:: O(n^2)

tryalgo.dyn_prog_tricks.opt_bin_search_tree2(success, failure)[source]#

Optimal binary search tree on elements from 1 to n

Parameters:

success – n+1 dimensional array with frequency of every element i. success[0] is ignored
failure – n+1 dimensional array with frequency between the elements, failure[i] is frequency of a query strictly between element i and i+1. These arrays do not have to be normalized.

Returns:

The value of an optimal search tree and the matrix with the roots for each subproblem, encoding the actual tree.

Complexity:

O(n^2)

tryalgo.edmonds_karp module#

Maximum flow by Edmonds-Karp

jill-jênn vie et christoph dürr - 2015-2019

tryalgo.edmonds_karp.edmonds_karp(graph, capacity, source, target)[source]#

Maximum flow by Edmonds-Karp

Parameters:

graph – directed graph in listlist or listdict format
capacity – in matrix format or same listdict graph
source (int) – vertex
target (int) – vertex

Returns:

flow matrix, flow value

Complexity:

$O(|V|*|E|^2)$

tryalgo.eulerian_tour module#

Eulerian cycle

jill-jênn vie et christoph dürr - 2015-2023

tryalgo.eulerian_tour.eulerian_tour_directed(graph)[source]#

Eulerian tour on a directed graph

Parameters:: graph – directed graph in listlist format, cannot be listdict
Assumes:: graph is eulerian
Returns:: eulerian cycle as a vertex list
Complexity:: O(|V|+|E|)

tryalgo.eulerian_tour.eulerian_tour_undirected(graph)[source]#

Eulerian tour on an undirected graph

Parameters:: graph – directed graph in listlist format, cannot be listdict
Assumes:: graph is eulerian
Returns:: eulerian cycle as a vertex list
Complexity:: O(|V|+|E|)

tryalgo.eulerian_tour.is_eulerian_tour_directed(graph, tour)[source]#

Test if a given tour is Eulerian for a directed graph

Parameters:

graph – directed graph in listlist format, cannot be listdict
tour – vertex list

Returns:

True if tour is eulerian

Complexity:

O(|V|*|E|) under the assumption that set membership is in constant time

tryalgo.eulerian_tour.is_eulerian_tour_undirected(graph, tour)[source]#

Test if a given tour is Eulerian for an undirected graph

Parameters:

graph – undirected graph in listlist format, cannot be listdict
tour – vertex list

Returns:

True if tour is eulerian

Complexity:

O(|V|*|E|) under the assumption that set membership is in constant time

tryalgo.eulerian_tour.random_eulerien_graph(n)[source]#

Generates some random eulerian graph

Parameters:: n (int) – number of vertices
Returns:: undirected graph in listlist representation
Complexity:: linear

tryalgo.eulerian_tour.write_cycle(filename, graph, cycle, directed)[source]#

Write an eulerian tour in DOT format

Parameters:

filename – the file to be written in DOT format
graph – graph in listlist format, cannot be listdict
directed (bool) – describes the graph
cycle – tour as a vertex list

Returns:

nothing

Complexity:

O(|V|^2 + |E|)

tryalgo.fast_exponentiation module#

Fast Exponentiation

jill-jenn vie et christoph durr and louis abraham - 2014-2018

tryalgo.fast_exponentiation.fast_exponentiation(a, b, q)[source]#

Compute (a pow b) % q, alternative shorter implementation

Parameters:

b (int a) – non negative
q (int) – positive

Complexity:

O(log b)

tryalgo.fast_exponentiation.fast_exponentiation2(a, b, q)[source]#

Compute (a pow b) % q

Parameters:

b (int a) – non negative
q (int) – positive

Complexity:

O(log b)

tryalgo.fenwick module#

Fenwick tree

jill-jenn vie et christoph durr - 2014-2018

class tryalgo.fenwick.Fenwick(t)[source]#

Bases: object

maintains a tree to allow quick updates and queries

add(a, val)[source]#

Parameters:: a (int) – index in t
Modifies:: adds val to t[a]

get(a)[source]#

Variant, reads t[a]

Parameters:: i (int) – negative a will return 0

intervalAdd(a, b, val)[source]#

Variant, adds val to t[a], to t[a + 1] … and to t[b]

Parameters:: b (int a) – with 0 <= a <= b < len(t)

intervalSum(a, b)[source]#

Parameters:: b (int a) – with 0 <= a <= b
Returns:: t[a] + … + t[b]

prefixSum(a)[source]#

Parameters:: a (int) – index in t, negative a will return 0
Returns:: t[0] + … + t[a]

class tryalgo.fenwick.FenwickMin(size)[source]#

Bases: object

maintains a tree to allow quick updates and queries of a virtual table t

prefixMin(a)[source]#

Parameters:: a (int) – index in t, negative a will return infinity
Returns:: min(t[0], … ,t[a])

update(a, val)[source]#

Parameters:

a (int) – index in t
val – a value

Modifies:

sets t[a] to the minimum of t[a] and val

tryalgo.fft module#

Fast Fourier Transformation

christoph dürr - jill-jênn vie - 2022

tryalgo.fft.fft(x)[source]#: Fast Fourier Transformation :input x: list of coefficients. Length n has to be a power of 2. :returns: list of sample values. :complexity: O(n log n).

tryalgo.fft.inv_fft(y)[source]#: Inverse Fast Fourier Transformation :input y: list of sample values. Length n has to be a power of 2. :returns: list of coefficients. :complexity: O(n log n).

tryalgo.fft.mul_poly_fft(p, q)[source]#: Multiply two polynomials in integer coefficient representation :complexity: O(n log n)

tryalgo.fft.pad(x)[source]#: pad array x with zeros to make its length a power of two :complexity: linear

tryalgo.floyd_warshall module#

All pairs shortest paths by Floyd-Warshall

jill-jênn vie, christoph dürr et pascal ortiz - 2014-2019

tryalgo.floyd_warshall.floyd_warshall(weight)[source]#

All pairs shortest paths by Floyd-Warshall

Parameters:: weight – edge weight matrix
Modifies:: weight matrix to contain distances in graph
Returns:: True if there are negative cycles
Complexity:: $O(|V|^3)$

tryalgo.floyd_warshall.floyd_warshall2(weight)[source]#

All pairs shortest paths by Floyd-Warshall. An improved implementation by Pascal-Ortiz

Parameters:: weight – edge weight matrix
Modifies:: weight matrix to contain distances in graph
Returns:: True if there are negative cycles
Complexity:: $O(|V|^3)$

tryalgo.ford_fulkerson module#

Maximum flow by Ford-Fulkerson

jill-jenn vie et christoph durr - 2014-2018

tryalgo.ford_fulkerson.ford_fulkerson(graph, capacity, s, t)[source]#

Maximum flow by Ford-Fulkerson

Parameters:

graph – directed graph in listlist or listdict format
capacity – in matrix format or same listdict graph
s (int) – source vertex
t (int) – target vertex

Returns:

flow matrix, flow value

Complexity:

O(|V|*|E|*max_capacity)

tryalgo.freivalds module#

Test matrix product AB = C by Freivalds

jill-jênn vie et christoph dürr - 2015-2020

tryalgo.freivalds.freivalds(A, B, C)[source]#

Tests matrix product AB=C by Freivalds

Parameters:

A – n by n numerical matrix
B – same
C – same

Returns:

False with high probability if AB != C

Complexity:

$O(n^2)$

tryalgo.gale_shapley module#

Stable matching by Gale-Shapley

jill-jênn vie et christoph durr - 2014-2019

tryalgo.gale_shapley.gale_shapley(men, women)[source]#

Stable matching by Gale-Shapley

Parameters:

men – table of size n, men[i] is preference list of women for men i
women – similar

Returns:

matching table, from women to men

Complexity:

$O(n^2)$

tryalgo.gauss_jordan module#

Linear equation system Ax=b by Gauss-Jordan

jill-jenn vie et christoph durr - 2014-2018

tryalgo.gauss_jordan.gauss_jordan(A, x, b)[source]#

Linear equation system Ax=b by Gauss-Jordan

Parameters:

A – m by n matrix
x – table of size n
b – table of size m

Modifies:

x will contain solution if any

Returns int:

0 if no solution, 1 if solution unique, 2 otherwise

Complexity:

$O(n^2m)$

tryalgo.graph module#

Reading graphs from files and writing into files

jill-jênn vie et christoph dürr - 2015-2019

class tryalgo.graph.GraphNamedVertices[source]#

Bases: object

add_arc(name_u, name_v, weight_uv=None)[source]#: Adds an arc between two given nodes, eventually with a given arc weight. In case of multiple arcs between the same pairs of nodes, only the lightest one is kept. Adds the given nodes, if they are not already present.

add_edge(name_u, name_v, weight_uv=None)[source]#

add_node(name)[source]#

tryalgo.graph.add_reverse_arcs(graph, capac=None)[source]#

Utility function for flow algorithms that need for every arc (u,v), the existence of an (v,u) arc, by default with zero capacity. graph can be in adjacency list, possibly with capacity matrix capac. or graph can be in adjacency dictionary, then capac parameter is ignored.

Parameters:

capac – arc capacity matrix
graph – in listlist representation, or in listdict representation, in this case capac is ignored

Complexity:

linear

Returns:

nothing, but graph is modified

tryalgo.graph.dictdict_to_listdict(dictgraph)[source]#

Transforms a dict-dict graph representation into a adjacency dictionary representation (list-dict)

Parameters:: dictgraph – dictionary mapping vertices to dictionary such that dictgraph[u][v] is weight of arc (u,v)
Complexity:: linear
Returns:: tuple with graph (listdict), name_to_node (dict), node_to_name (list)

tryalgo.graph.extract_path(prec, v)[source]#

extracts a path in form of vertex list from source to vertex v: given a precedence table prec leading to the source

Parameters:

prec – precedence table of a tree
v – vertex on the tree

Returns:

path from root to v, in form of a list

Complexity:

linear

tryalgo.graph.listdict_to_listlist_and_matrix(sparse)[source]#

Transforms the adjacency list representation of a graph of type listdict into the listlist + weight matrix representation

Parameters:: sparse – graph in listdict representation
Returns:: couple with listlist representation, and weight matrix
Complexity:: linear

tryalgo.graph.listlist_and_matrix_to_listdict(graph, weight=None)[source]#

Transforms the weighted adjacency list representation of a graph of type listlist + optional weight matrix into the listdict representation

Parameters:

graph – in listlist representation
weight – optional weight matrix

Returns:

graph in listdict representation

Complexity:

linear

tryalgo.graph.make_flow_labels(graph, flow, capac)[source]#

Generate arc labels for a flow in a graph with capacities.

Parameters:

graph – adjacency list or adjacency dictionary
flow – flow matrix or adjacency dictionary
capac – capacity matrix or adjacency dictionary

Returns:

listdic graph representation, with the arc label strings

tryalgo.graph.matrix_to_listlist(weight)[source]#

transforms a squared weight matrix in a adjacency table of type listlist encoding the directed graph corresponding to the entries of the matrix different from None

Parameters:: weight – squared weight matrix, weight[u][v] != None iff arc (u, v) exists
Complexity:: linear
Returns:: the unweighted directed graph in the listlist representation, listlist[u] contains all v for which arc (u,v) exists.

tryalgo.graph.read_graph(filename, directed=False, weighted=False, default_weight=None)[source]#

Read a graph from a text file

Parameters:

filename – plain text file. All numbers are separated by space. Starts with a line containing n (#vertices) and m (#edges). Then m lines follow, for each edge. Vertices are numbered from 0 to n-1. Line for unweighted edge u,v contains two integers u, v. Line for weighted edge u,v contains three integers u, v, w[u,v].
directed – true for a directed graph, false for undirected
weighted – true for an edge weighted graph

Returns:

graph in listlist format, possibly followed by weight matrix

Complexity:

O(n + m) for unweighted graph, $O(n^2)$ for weighted graph

tryalgo.graph.readtab(fi, ty)[source]#

Reads a line from file with a space separated list: of items of type ty

Parameters:

file – input stream, for example sys.stdin
ty – a type, for example int

Returns:

a tuple with elements of type ty

tryalgo.graph.readval(file, ty)[source]#

Reads a line from file with an item of type ty

Parameters:

file – input stream, for example sys.stdin
ty – a type, for example int

Returns:

an element of type ty

tryalgo.graph.tree_adj_to_prec(graph, root=0)[source]#

Transforms a tree given as adjacency list into predecessor table form. if graph is not a tree: will return a DFS spanning tree

Parameters:: graph – directed graph in listlist or listdict format
Returns:: tree in predecessor table representation
Complexity:: linear

tryalgo.graph.tree_prec_to_adj(prec, root=0)[source]#

Transforms a tree given as predecessor table into adjacency list form

Parameters:

prec – predecessor table representing a tree, prec[u] == v iff u is successor of v, except for the root where prec[root] == root
root – root vertex of the tree

Returns:

undirected graph in listlist representation

Complexity:

linear

tryalgo.graph.write_graph(dotfile, graph, directed=False, node_label=None, arc_label=None, comment='', node_mark={}, arc_mark={})[source]#

Writes a graph to a file in the DOT format

Parameters:

dotfile – the filename.
graph – directed graph in listlist or listdict format
directed – true if graph is directed, false if undirected
weight – in matrix format or same listdict graph or None
node_label – vertex label table or None
arc_label – arc label matrix or None
comment – comment string for the dot file or None
node_mark – set of nodes to be shown in gray
arc_marc – set of arcs to be shown in red

Complexity:

O(|V| + |E|)

tryalgo.graph01 module#

Shortest path in a 0,1 weighted graph

jill-jenn vie et christoph durr - 2014-2018

tryalgo.graph01.dist01(graph, weight, source=0, target=None)[source]#

Shortest path in a 0,1 weighted graph

Parameters:

graph – directed graph in listlist or listdict format
weight – matrix or adjacency dictionary
source (int) – vertex
target – exploration stops once distance to target is found

Returns:

distance table, predecessor table

Complexity:

O(|V|+|E|)

tryalgo.hamiltonian_cycle module#

Hamiltonian Cycle

jill-jenn vie et christoph durr - 2023

tryalgo.hamiltonian_cycle.hamiltonian_cycle(weight)[source]#

Hamiltonian Cycle

Parameters:: weight – matrix of edge weights of a complete graph
Returns:: minimum weight of a Hamiltonian cycle
Complexity:: O(n^2 2^n)

tryalgo.horn_sat module#

Solving Horn SAT

christoph dürr - 2016-2020

clauses are numbered starting from 0 variables are strings (identifier)

solution : set of variables that are set to true posvar_in_clause : maps clause to the unique positive variable in clause (or None) clause_with_negvar : maps variable v to all clauses that contain not(v)

every clause has a score: number of its negative variables that are not in solution sol pool : maps score to clauses of that score

tryalgo.horn_sat.horn_sat(formula)[source]#

Solving a HORN Sat formula

Parameters:: formula – list of couple(posvar, negvars). negvars is a list of the negative variables (can be empty) posvar is the positive variable (can be None) Variables can be any hashable objects: integers, strings…
Returns:: None if formula is not satisfiable, else a minimal set of vars that have to be set to true in order to satisfy the formula.
Complexity:: linear

tryalgo.horn_sat.read(filename)[source]#

reads a Horn SAT formula from a text file

File format:: # comment A # clause with unique positive literal :- A # clause with unique negative literal A :- B, C, D # clause where A is positive and B,C,D negative # variables are strings without spaces

tryalgo.huffman module#

Huffman code

jill-jenn vie et christoph durr - 2014-2022

tryalgo.huffman.extract(code, tree, prefix)[source]#

Extract Huffman code from a Huffman tree

Parameters:

code – a dictionary that will contain the constructed code. should initially be empty.
tree – a node of the tree. Leafs are of the form (frequency, symbol). Inner nodes are of the form [left_sub_tree, right_sub_tree].
prefix – a list with the 01 characters encoding the path from the root to the node tree

Complexity:

O(n), where n = number of nodes in tree

tryalgo.huffman.huffman(freq)[source]#

Huffman code

Parameters:: freq – dictionary with frequencies for each item
Returns:: dictionary with binary code string for each item
Complexity:: O(n log n), where n = len(freq)

tryalgo.interval_cover module#

Minimum interval cover

jill-jênn vie et christoph dürr - 2014-2020

tryalgo.interval_cover.interval_cover(I)[source]#

Minimum interval cover

Parameters:: I – list of closed intervals
Returns:: minimum list of points covering all intervals
Complexity:: O(n log n)

tryalgo.interval_tree module#

Interval tree

christoph dürr - jill-jênn vie - 2013-2018

tryalgo.interval_tree.interval_tree(intervals)[source]#

Construct an interval tree

Parameters:: intervals – list of half-open intervals encoded as value pairs [left, right)
Assumes:: intervals are lexicographically ordered >>> assert intervals == sorted(intervals)
Returns:: the root of the interval tree
Complexity:: $O(n)$

tryalgo.interval_tree.intervals_containing(t, p)[source]#

Query the interval tree

Parameters:

t – root of the interval tree
p – value

Returns:

a list of intervals containing p

Complexity:

O(log n + m), where n is the number of intervals in t, and m the length of the returned list

tryalgo.intervals_union module#

Union of intervals

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.intervals_union.intervals_union(S)[source]#

Union of intervals

Parameters:: S – list of pairs (low, high) defining intervals [low, high)
Returns:: ordered list of disjoint intervals with the same union as S
Complexity:: O(n log n)

tryalgo.karatsuba module#

Karatsuba multiplication of polynomials

christoph dürr - jill-jênn vie - 2022

tryalgo.karatsuba.add_poly(P, Q)[source]#: Add two polynomials represented by their coefficients. :param P, Q: two vectors representing polynomials :returns: a vector representing the addition :complexity: linear in the size of P and Q.

tryalgo.karatsuba.eval_poly(P, x)[source]#: evaluate a polynomial in x. :param P: an array representing the polynomial :returns: the value of P(x) :complexity: linear in the size of P.

tryalgo.karatsuba.mul_poly(P, Q)[source]#: Karatsuba’s algorithm. Multiply two polynomials represented by their coefficients. i.e. P(x) = sum P[i] x**i. :param P, Q: two vectors representing polynomials :returns: a vector representing the product :complexity: $O(n^{log_2 3})=O(n^{1.585})$, where n is total degree of P and Q.

tryalgo.karatsuba.sub_poly(P, Q)[source]#: Subtruct two polynomials represented by their coefficients. :param P, Q: two vectrs representing polynomials :returns: a vector representing the difference :complexity: linear in the size of P and Q.

tryalgo.knapsack module#

Knapsack

jill-jênn vie et christoph dürr - 2015-2019

tryalgo.knapsack.knapsack(p, v, cmax)[source]#

Knapsack problem: select maximum value set of items if total size not more than capacity

Parameters:

p – table with size of items
v – table with value of items
cmax – capacity of bag

Requires:

number of items non-zero

Returns:

value optimal solution, list of item indexes in solution

Complexity:

O(n * cmax), for n = number of items

tryalgo.knapsack.knapsack2(p, v, cmax)[source]#

Knapsack problem: select maximum value set of items if total size not more than capacity. alternative implementation with same behavior.

Parameters:

p – table with size of items
v – table with value of items
cmax – capacity of bag

Requires:

number of items non-zero

Returns:

value optimal solution, list of item indexes in solution

Complexity:

O(n * cmax), for n = number of items

tryalgo.knuth_morris_pratt module#

Find the length of maximal borders by Knuth-Morris-Pratt

jill-jênn vie, christoph dürr et louis abraham - 2014-2019 inspired from a practical lesson (TP) from Yves Lemaire

tryalgo.knuth_morris_pratt.knuth_morris_pratt(s, t)[source]#

Find a substring by Knuth-Morris-Pratt

Parameters:

s – the haystack string
t – the needle string

Returns:

index i such that s[i: i + len(t)] == t, or -1

Complexity:

O(len(s) + len(t))

tryalgo.knuth_morris_pratt.maximum_border_length(w)[source]#

Maximum string borders by Knuth-Morris-Pratt

Parameters:: w – string
Returns:: table f such that f[i] is the longest border length of w[:i + 1]
Complexity:: linear

tryalgo.knuth_morris_pratt.powerstring_by_border(u)[source]#

Power string by Knuth-Morris-Pratt

Parameters:: u – string
Returns:: largest k such that there is a string y with u = y^k
Complexity:: O(len(u))

tryalgo.knuth_morris_pratt.powerstring_by_find(u)[source]#

Power string using the python find method

Parameters:: u – string
Returns:: largest k such that there is a string y with u = y^k
Complexity:: O(len(u)^2), this is due to the naive implementation of string.find

tryalgo.kruskal module#

Minimum spanning tree by kruskal

jill-jenn vie et christoph durr - 2014-2018

class tryalgo.kruskal.UnionFind(n)[source]#

Bases: object

Maintains a partition of {0, …, n-1}

find(x_index)[source]#

Returns:: identifier of part containing x_index
Complex_indexity:: O(inverse_ackerman(n))

union(x_index, y_index)[source]#: Merges part that contain x and part containing y :returns: False if x_index, y_index are already in same part :complexity: O(inverse_ackerman(n))

tryalgo.kruskal.dist(a, b)[source]#: distance between point a and point b

tryalgo.kruskal.kruskal(graph, weight)[source]#

Minimum spanning tree by Kruskal

Parameters:

graph – undirected graph in listlist or listdict format
weight – in matrix format or same listdict graph

Returns:

list of edges of the tree

Complexity:

O(|E|log|E|)

tryalgo.kuhn_munkres module#

Maximum profit bipartite matching by Kuhn-Munkres

jill-jenn vie, christoph durr and samuel tardieu - 2014-2019

primal LP

max sum_{u,v} w[u,v] * x[u,v]

such that for all u in U: sum_v x[u,v] == 1 (l[u])

for all v in V: sum_u x[u,v] <= 1 (l[v])

for all u,v: x[u,v] >= 0

dual LP

min sum_u l[u] + sum_v l[v]

such that for all u,v: l[u] + l[v] >= w[u,v] (*)

for all u in U: l[u] is arbitrary (free variable) for all v in V: l[v] >= 0

primal-dual algorithm:

Start with trivial solution l for dual and with trivial non-solution x for primal.

Iteratively improve primal or dual solution, maintaining complementary slackness conditions.

tryalgo.kuhn_munkres.kuhn_munkres(G, TOLERANCE=1e-06)[source]#

Maximum profit bipartite matching by Kuhn-Munkres

Parameters:

G – weight matrix where G[u][v] is the weight of edge (u,v),
TOLERANCE – a value with absolute value below tolerance is considered as being zero. If G consists of integer or fractional values then TOLERANCE can be chosen 0.

Requires:

graph (U,V,E) is complete bi-partite graph with len(U) <= len(V) float(‘-inf’) or float(‘inf’) entries in G are allowed but not None.

Returns:

matching table from U to V, value of matching

Complexity:

$O(|U|^2 |V|)$

tryalgo.kuhn_munkres_n4 module#

kuhn_munkres_n4

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.kuhn_munkres_n4.kuhn_munkres(G)[source]#

Maximum profit perfect matching

for minimum cost perfect matching just inverse the weights

Parameters:: G – squared weight matrix of a complete bipartite graph
Complexity:: $O(n^4)$

tryalgo.laser_mirrors module#

Orienting mirrors to allow connectivity by a laser beam

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.laser_mirrors.laser_mirrors(rows, cols, mir)[source]#

Orienting mirrors to allow reachability by laser beam

Parameters:

rows (int) –
cols (int) – rows and cols are the dimension of the grid
mir – list of mirror coordinates, except mir[0]= laser entrance, mir[-1]= laser exit.

Complexity:

$O(2^n)$

tryalgo.laser_mirrors.solve(succ, orien, i, direc)[source]#

Can a laser leaving mirror i in direction direc reach exit ?

Parameters:

i – mirror index
direc – direction leaving mirror i
orient – orient[i]=orientation of mirror i
succ – succ[i][direc]=succ mirror reached when leaving i in direction direc

tryalgo.left_right_inversions module#

Left and right inversions in a table

christoph dürr - 2016-2019

tryalgo.left_right_inversions.left_right_inversions(tab)[source]#

Compute left and right inversions of each element of a table.

Parameters:: tab – list with comparable elements
Returns:: lists left and right. left[j] = the number of i<j such that tab[i] > tab[j]. right[i] = the number of i<j such that tab[i] > tab[j].
Complexity:: O(n log n)

tryalgo.levenshtein module#

Levenshtein edit distance

jill-jenn vie et christoph durr - 2014-2018

tryalgo.levenshtein.levenshtein(x, y)[source]#

Levenshtein edit distance

Parameters:

x –
y – strings

Returns:

distance

Complexity:

O(|x|*|y|)

tryalgo.longest_common_subsequence module#

Longest increasing subsequence

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.longest_common_subsequence.longest_common_subsequence(x, y)[source]#

Longest common subsequence

Dynamic programming

Parameters:

x –
y – x, y are lists or strings

Returns:

longest common subsequence in form of a string

Complexity:

O(|x|*|y|)

tryalgo.longest_increasing_subsequence module#

Longest increasing subsequence

jill-jenn vie et christoph durr - 2014-2018

tryalgo.longest_increasing_subsequence.longest_increasing_subsequence(x)[source]#

Longest increasing subsequence

Parameters:: x – sequence
Returns:: longest strictly increasing subsequence y
Complexity:: O(|x|*log(|y|))

tryalgo.lowest_common_ancestor module#

Lowest common ancestor

jill-jenn vie et christoph durr - 2014-2018

class tryalgo.lowest_common_ancestor.LowestCommonAncestorRMQ(graph)[source]#

Bases: object

Lowest common ancestor data structure using a reduction to range minimum query

query(u, v)[source]#

Returns:: the lowest common ancestor of u and v
Complexity:: O(log n)

class tryalgo.lowest_common_ancestor.LowestCommonAncestorShortcuts(prec)[source]#

Bases: object

Lowest common ancestor data structure using shortcuts to ancestors

query(u, v)[source]#

Returns:: the lowest common ancestor of u and v
Complexity:: O(log n)

tryalgo.lowest_common_ancestor.log2ceil(n)[source]#: log of n in base 2 rounded up

tryalgo.lowest_common_ancestor.log2floor(n)[source]#: log of n in base 2 rounded down

tryalgo.majority module#

Majority

jill-jenn vie et christoph durr - 2014-2019

tryalgo.majority.majority(L)[source]#

Majority

Parameters:: L – list of elements
Returns:: element that appears most in L, tie breaking with smallest element
Complexity:: $O(nk)$ in average, where n = len(L) and k = max(w for w in L) $O(n^2k)$ in worst case due to the use of a dictionary

tryalgo.manacher module#

Longest palindrome in a string by Manacher

jill-jênn vie et christoph dürr - 2014-2019

http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Algorithme de Manacher problème: plus long palindrome entrée: chaîne s sortie: indices i, j tel que s[i:j] est un palindrome et que j-i est maximal et i maximal complexité: temps linéaire

tous les indices réfèrent à une chaîne fictive t de la forme “^#a#b#a#a#$” si s=”abaa” invariant: pour chaque préfixe vu on maintient un palindrome centré en c et de bord droit r qui maximise r ainsi que p[i] = plus grand rayon d’un palindrome centré en i

tryalgo.manacher.manacher(s)[source]#

Longest palindrome in a string by Manacher

Parameters:: s – string
Requires:: s is not empty
Returns:: i,j such that s[i:j] is the longest palindrome in s
Complexity:: O(len(s))

tryalgo.matrix_chain_mult module#

Matrix chain multiplication multiplication de matrices

jill-jenn vie et christoph durr - 2014-2018

tryalgo.matrix_chain_mult.matrix_chain_mult(M)[source]#

Matrix chain multiplication

Parameters:: M – list of matrices
Returns:: M[0] * … * M[-1], computed in time optimal order
Complexity:: whatever is needed by the multiplications

tryalgo.matrix_chain_mult.matrix_mult_opt_order(M)[source]#

Matrix chain multiplication optimal order

Parameters:: M – list of matrices
Returns:: matrices opt, arg, such that opt[i][j] is the optimal number of operations to compute M[i] * … * M[j] when done in the order (M[i] * … * M[k]) * (M[k + 1] * … * M[j]) for k = arg[i][j]
Complexity:: $O(n^3)$

tryalgo.max_interval_intersec module#

Sweepline algorithm technique

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.max_interval_intersec.max_interval_intersec(S)[source]#

determine a value that is contained in a largest number of given intervals

Parameters:: S – list of half open intervals
Complexity:: O(n log n), where n = len(S)

tryalgo.merge_ordered_lists module#

Merge two ordered lists

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.merge_ordered_lists.merge(x, y)[source]#

Merge two ordered lists

Parameters:

x –
y – x, y are nondecreasing ordered lists

Returns:

union of x and y in order

Complexity:

linear

tryalgo.min_mean_cycle module#

Minimum mean cycle by Karp

jill-jenn vie et christoph durr - 2014-2018

tryalgo.min_mean_cycle.min_mean_cycle(graph, weight, start=0)[source]#

Minimum mean cycle by Karp

Parameters:

graph – directed graph in listlist or listdict format
weight – in matrix format or same listdict graph
start (int) – vertex that should be contained in cycle

Returns:

cycle as vertex list, average arc weights or None if there is no cycle from start

Complexity:

O(|V|*|E|)

tryalgo.next_permutation module#

Next permutation prochaine permuation

jill-jênn vie et christoph dürr - 2014-2020

tryalgo.next_permutation.convert(word, ass)[source]#: solves a cryptogram in the style SEND + MORE = MONEY

tryalgo.next_permutation.next_permutation(tab)[source]#

find the next permutation of tab in the lexicographical order

Parameters:: tab – table with n elements from an ordered set
Modifies:: table to next permutation
Returns:: False if permutation is already lexicographical maximal
Complexity:: O(n)

tryalgo.next_permutation.solve_word_addition(S)[source]#: returns number of solutions

tryalgo.our_heap module#

A min heap

christoph dürr et jill-jênn vie - 2015-2019

class tryalgo.our_heap.OurHeap(items)[source]#

Bases: object

min heap

heap: is the actual heap, heap[1] = index of the smallest element
rank: inverse of heap with rank[x]=i iff heap[i]=x
n: size of the heap

Complexity:: init O(n log n), len O(1), other operations O(log n) in expectation and O(n) in worst case, due to the usage of a dictionary

down(i)[source]#: the value of heap[i] has increased. Maintain heap invariant.

pop()[source]#: Remove and return smallest element

push(x)[source]#: Insert new element x in the heap. Assumption: x is not already in the heap

up(i)[source]#: The value of heap[i] has decreased. Maintain heap invariant.

update(old, new)[source]#: Replace an element in the heap

tryalgo.our_queue module#

A FIFO queue

christoph dürr - jill-jênn vie - 2015-2019

class tryalgo.our_queue.OurQueue[source]#

Bases: object

A FIFO queue

Complexity:: all operators in amortized constant time, except __str__ which is linear

pop()[source]#

push(obj)[source]#

tryalgo.our_std module#

Our Standards

Jill-Jênn Vie et Christoph Dürr - 2020

tryalgo.our_std.readarray(typ)[source]#: function to read an array

tryalgo.our_std.readint()[source]#: function to read an integer from stdin

tryalgo.our_std.readmatrix(n)[source]#: function to read a matrix

tryalgo.our_std.readstr()[source]#: function to read a string from stdin

tryalgo.pareto module#

Pareto sets

jill-jenn vie et christoph durr - 2022

tryalgo.pareto.pareto2d(points)[source]#

Compute the Pareto set of a given set of points in 2 dimensions

Parameters:: points – list of tuples with the coordinates of the points. Can be floating point coordinates.
Modifies:: points will be sorted
Returns:: a list of non-dominated points
Complexity:: $O(nlog n)$

tryalgo.pareto.pareto3d(points)[source]#

Compute the Pareto set of a given set of points in 2 dimensions

Parameters:: points – list of tuples with the coordinates of the points. Can be floating point coordinates.
Modifies:: points will be sorted
Returns:: a list of non-dominated points
Complexity:: $O(nlog n)$

tryalgo.partition_refinement module#

Partition refinement

christoph dürr - 2016-2019

log: 10/11/2016 modified to preserve class order after refinement: 15/11/2016 this was nonsense, moved back

class tryalgo.partition_refinement.PartitionRefinement(n)[source]#

Bases: object

This data structure implements an order preserving partition with refinements.

order()[source]#: Produce a flatten list of the partition, ordered by classes

refine(pivot)[source]#: Split every class C in the partition into C intersection pivot and C setminus pivot complexity: linear in size of pivot

tolist()[source]#: produce a list representation of the partition

tryalgo.permutation_rank module#

Permutation rank

christoph dürr - 2016-2019

tryalgo.permutation_rank.permutation_rank(p)[source]#

Given a permutation of {0,..,n-1} find its rank according to lexicographical order

param p:

list of length n containing all integers from 0 to n-1

returns:

rank between 0 and n! -1

beware:

computation with big numbers

complexity:

O(n^2)

tryalgo.permutation_rank.rank_permutation(r, n)[source]#

Given r and n find the permutation of {0,..,n-1} with rank according to lexicographical order equal to r

param r n:

integers with 0 ≤ r < n!

returns:

permutation p as a list of n integers

beware:

computation with big numbers

complexity:

O(n^2)

tryalgo.polygon module#

Area of polygone mesures polygone

jill-jenn vie et christoph durr - 2014-2018

tryalgo.polygon.area(p)[source]#

Area of a polygone

Parameters:: p – list of the points taken in any orientation, p[0] can differ from p[-1]
Returns:: area
Complexity:: linear

tryalgo.polygon.is_simple(polygon)[source]#

Test if a rectilinear polygon is is_simple

Parameters:: polygon – list of points as (x,y) pairs along the closed polygon
Returns:: True if the segements do not intersect
Complexity:: O(n log n) for n=len(polygon)

tryalgo.predictive_text module#

Predictive text for mobile phones

jill-jenn vie et christoph durr and louis abraham - 2014-2019

tryalgo.predictive_text.predictive_text(dic)[source]#

Predictive text for mobile phones

Parameters:: dic – associates weights to words from [a-z]*
Returns:: a dictionary associating to words from [2-9]* a corresponding word from the dictionary with highest weight
Complexity:: linear in total word length

tryalgo.predictive_text.propose(prop, seq)[source]#: wrapper to access a dictionary even for non-present keys

tryalgo.primes module#

Prime numbers by Eratosthene nombre premiers <n

jill-jenn vie et christoph durr - 2014-2018

tryalgo.primes.eratosthene(n)[source]#

Prime numbers by sieve of Eratosthene

Parameters:: n – positive integer
Assumes:: n > 2
Returns:: list of prime numbers <n
Complexity:: O(n loglog n)

tryalgo.primes.gries_misra(n)[source]#

Prime numbers by the sieve of Gries-Misra Computes both the list of all prime numbers less than n, and a table mapping every integer 2 ≤ x < n to its smallest prime factor

Parameters:: n – positive integer
Returns:: list of prime numbers, and list of prime factors
Complexity:: O(n)

tryalgo.rabin_karp module#

Find substrings by Rabin-Karp

jill-jenn vie et christoph durr - 2015-2019

tryalgo.rabin_karp.matches(s, t, i, j, k)[source]#: Checks whether s[i:i + k] is equal to t[j:j + k]. We used a loop to ease the implementation in other languages.

tryalgo.rabin_karp.rabin_karp_factor(s, t, k)[source]#

Find a common factor by Rabin-Karp

Parameters:

s (string) – haystack
t (string) – needle
k (int) – factor length

Returns:

(i, j) such that s[i:i + k] == t[j:j + k] or None. In case of tie, lexicographical minimum (i, j) is returned

Complexity:

O(len(s) + len(t)) in expected time, and O(len(s) + len(t) * k) in worst case

tryalgo.rabin_karp.rabin_karp_matching(s, t)[source]#

Find a substring by Rabin-Karp

Parameters:

s – the haystack string
t – the needle string

Returns:

index i such that s[i: i + len(t)] == t, or -1

Complexity:

O(len(s) + len(t)) in expected time, and O(len(s) * len(t)) in worst case

tryalgo.rabin_karp.roll_hash(old_val, out_digit, in_digit, last_pos)[source]#

tryalgo.range_minimum_query module#

Range minimum query Minimum d’une plage — range minimum query

jill-jenn vie et christoph durr - 2014-2019

class tryalgo.range_minimum_query.LazySegmentTree(tab)[source]#

Bases: object

maintains a tree to allow quick updates and queries on a table.

This is more general than a Fenwick tree or a tree for MinRangeQuery. Here queries and updates act on index ranges. Updates can be set a range to a value or add a value to a range. Queries can be max, min and sum over an index range. All operations run in time O(log n) for a the table size n. The given ranges are in the form [i,j] where i is included and j excluded. In the recursive calls, node is the index of a node in the tree, and left, right its range. Values can be any numerical values allowing max, min, and sum, such as integers, floating point numbers or fractions (from the class Fraction). Updates over an empty range is valid and does nothing. Queries over an empty range is valid and returns the neutral value -inf, +inf or 0.

If the node is cleared, then maxval, minval, sumval represent for each node the query responses over the corresponding index ranges. If the node is not clean, it means that lazyset and/or lazyadd contain suspendet update instructions for that node. Clearing a node means propagating these values to the descents in the subtrees, and updating maxval,minval and sumval for that node.

add(i, j, val)[source]#

max(i, j)[source]#

min(i, j)[source]#

set(i, j, val)[source]#

sum(i, j)[source]#

class tryalgo.range_minimum_query.RangeMinQuery(t, INF=inf)[source]#

Bases: object

Range minimum query

maintains a table t, can read/write items t[i], and query range_min(i,k) = min{ t[i], t[i + 1], …, t[k - 1]} :complexity: all operations in O(log n), for n = len(t)

range_min(i, k)[source]#

Returns:: min{ t[i], t[i + 1], …, t[k - 1]}
Complexity:: O(log len(t))

tryalgo.rectangles_from_grid module#

Largest area rectangle in a binary matrix plus grand rectangle monochromatique

jill-jenn vie et christoph durr - 2014-2018

tryalgo.rectangles_from_grid.rectangles_from_grid(P, black=1)[source]#

Largest area rectangle in a binary matrix

Parameters:

P – matrix
black – search for rectangles filled with value black

Returns:

area, left, top, right, bottom of optimal rectangle consisting of all (i,j) with left <= j < right and top <= i <= bottom

Complexity:

linear

tryalgo.rectangles_from_histogram module#

Largest Rectangular Area in a Histogram

jill-jenn vie et christoph durr - 2014-2018

tryalgo.rectangles_from_histogram.rectangles_from_histogram(H)[source]#

Largest Rectangular Area in a Histogram

Parameters:: H – histogram table
Returns:: area, left, height, right, rect. is [0, height] * [left, right)
Complexity:: linear

tryalgo.rectangles_from_points module#

How many rectangles can be formed from a set of points

jill-jenn vie et christoph durr - 2014-2018

tryalgo.rectangles_from_points.rectangles_from_points(S)[source]#

How many rectangles can be formed from a set of points

Parameters:: S – list of points, as coordinate pairs
Returns:: the number of rectangles
Complexity:: $O(n^2)$

tryalgo.roman_numbers module#

Evaluate an arithmetic expression

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.roman_numbers.int2roman(val)[source]#

Code roman number

Parameters:: val – integer between 1 and 9999
Returns:: the corresponding roman number
Complexity:: linear (if that makes sense for constant bounded input size)

tryalgo.roman_numbers.roman2int(s)[source]#

Decode roman number

Parameters:: s – string representing a roman number between 1 and 9999
Returns:: the decoded roman number
Complexity:: linear (if that makes sense for constant bounded input size)

tryalgo.scalar module#

Permute vector to minimize scalar product

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.scalar.min_scalar_prod(x, y)[source]#

Permute vector to minimize scalar product

Parameters:

x –
y – x, y are vectors of same size

Returns:

min sum x[i] * y[sigma[i]] over all permutations sigma

Complexity:

O(n log n)

tryalgo.shortest_cycle module#

Find shortest simple cycle

christoph durr, finn voelkel and louis abraham - 2016-2019

O(V*E) footnote (1) here you can add parity check of cycle_len if only even cycles are requested

tryalgo.shortest_cycle.powergraph(graph, k)[source]#

Compute the k-th: powergraph which has an edge u,v for every vertex pair of distance at most k in the given graph.

Parameters:

graph – undirected graph in listlist or listdict format
k – non-negative integer.

Complexity:

O(V^3)

tryalgo.shortest_cycle.shortest_cycle(graph)[source]#

Finding a shortest cycle in an undirected unweighted graph

Parameters:: graph – undirected graph in listlist or listdict format
Returns:: None or a list C describing a shortest cycle
Complexity:: O(|V|*|E|)

tryalgo.skip_list module#

skip-list

louis abraham - 2017-2019

Inspired by https://kunigami.blog/2012/09/25/skip-lists-in-python/ count contains the gap between the positions (https://www.cs.bgu.ac.il/~ds112/wiki.files/ds112_ps7.pdf)

class tryalgo.skip_list.AbstractSkipList[source]#

Bases: object

find(key, update=None)[source]#

getkth(k)[source]#: starts from 0

insert(node)[source]#

lastKey(key)[source]#: lastKey(key) < key

nextKey(key)[source]#: nextKey(key) >= key

nextNode(key, update=None)[source]#

static randomHeight()[source]#

remove(key)[source]#

class tryalgo.skip_list.SortedDict(iterable=())[source]#

Bases: AbstractSkipList

class Node(key, val, next, count)#

Bases: tuple

count#: Alias for field number 3

key#: Alias for field number 0

next#: Alias for field number 2

val#: Alias for field number 1

keys()[source]#

class tryalgo.skip_list.SortedSet(iterable=())[source]#

Bases: AbstractSkipList

class Node(key, next, count)#

Bases: tuple

count#: Alias for field number 2

key#: Alias for field number 0

next#: Alias for field number 1

add(key)[source]#

pop()[source]#: Pops the first element

tryalgo.skip_list.random() → x in the interval [0, 1).#

tryalgo.strongly_connected_components module#

Strongly connected components composantes fortement connexes

jill-jênn vie et christoph dürr - 2015-2018

tryalgo.strongly_connected_components.kosaraju(graph)[source]#

Strongly connected components by Kosaraju

Parameters:: graph – directed graph in listlist format, cannot be listdict
Returns:: list of lists for each component
Complexity:: linear

tryalgo.strongly_connected_components.reverse(graph)[source]#: replace all arcs (u, v) by arcs (v, u) in a graph

tryalgo.strongly_connected_components.tarjan(graph)[source]#

Strongly connected components by Tarjan, iterative implementation

Parameters:: graph – directed graph in listlist format, cannot be listdict
Returns:: list of lists for each component
Complexity:: linear

tryalgo.strongly_connected_components.tarjan_recursif(graph)[source]#

Strongly connected components by Tarjan, recursive implementation

Parameters:: graph – directed graph in listlist format, cannot be listdict
Returns:: list of lists for each component
Complexity:: linear

tryalgo.subsetsum module#

subsetsum

jill-jenn vie et christoph durr - 2015-2018

tryalgo.subsetsum.coin_change(x, R)[source]#

Coin change

Parameters:

x – table of non negative values
R – target value

Returns bool:

True if there is a non negative linear combination of x that has value R

Complexity:

O(n*R)

tryalgo.subsetsum.subset_sum(x, R)[source]#

Subsetsum

Parameters:

x – table of non negative values
R – target value

Returns bool:

True if a subset of x sums to R

Complexity:

O(n*R)

tryalgo.subsetsum_divide module#

Subsetsum by splitting

christoph dürr et jill-jênn vie - 2014-2019

tryalgo.subsetsum_divide.part_sum(x_table, i=0)[source]#

All subsetsums from x_table[i:]

Parameters:

x_table – table of values
i (int) – index_table defining suffix_table of x_table to be considered

Iterates:

over all values, in arbitrary order

Complexity:

$O(2^{len(x_table)-i})$

tryalgo.subsetsum_divide.part_sum2(x_table)[source]#

All subsetsums from a list x

Parameters:: x_table – list of values
Complexity:: $O(2^{len(x)})$

tryalgo.subsetsum_divide.subset_sum(x_table, r_target)[source]#

Subsetsum by splitting

Parameters:

x_table – table of values
r_target – target value

Returns bool:

if there is a subsequence of x_table with total sum r_target

Complexity:

$O(n^{\lceil n/2 \rceil})$

tryalgo.subsetsum_divide.subset_sum2(x_table, r_target)[source]#

Subsetsum by splitting

Parameters:

x_table – table of values
r_target – target value

Returns bool:

if there is a subsequence of x_table with total sum r_target

Complexity:

$O(n^{\lceil n/2 \rceil})$

tryalgo.sudoku module#

Solving Sudoku (nanpure)

jill-jenn vie et christoph durr - 2014-2019

tryalgo.sudoku.sudoku(G)[source]#

Solving Sudoku

Parameters:: G – integer matrix with 0 at empty cells
Returns bool:: True if grid could be solved
Modifies:: G will contain the solution
Complexity:: huge, but linear for usual published 9x9 grids

tryalgo.suffix_array module#

suffix array, but only the O(n log^2(n)) implementation, which is enough for most programming contest problems

christoph dürr 2024

tryalgo.suffix_array.sort_class(s)[source]#

sorts s and returns additional information

Parameters:: s – string or list
Returns p, c:: p[j]=i if s[i] has rank j in sorted(s) and c[i] is rank of s[i] in sorted(set(s))
Complexity:: O(n log n) or better if sort makes use of specific values in s

tryalgo.suffix_array.sort_cyclic_shifts(s)[source]#

given a string s, sort lexicographically all cyclic shifts of s.

The i-th cyclic shift of s is s[i:] + s[i:] :param s: string or list :returns L: such that L[j]=i if the i-th cyclic shift of s has rank j :complexity: O(n * log(n)^2)

tryalgo.suffix_array.suffix_array(s)[source]#: given a string s, sort lexicographically suffixes of s :param s: string :returns: R with R[i] is j such that s[j:] has rank i :complexity: O(n log^2 n)

tryalgo.three_partition module#

subsetsum

jill-jênn vie et christoph dürr - 2015-2019

tryalgo.three_partition.three_partition(x)[source]#

partition a set of integers in 3 parts of same total value

Parameters:: x – table of non negative values
Returns:: triplet of the integers encoding the sets, or None otherwise
Complexity:: $O(2^{2n})$

tryalgo.topological_order module#

Topological order

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.topological_order.topological_order(graph)[source]#

Topological sorting by maintaining indegree

Parameters:: graph – directed graph in listlist format, cannot be listdict
Returns:: list of vertices in order
Complexity:: O(|V|+|E|)

tryalgo.topological_order.topological_order_dfs(graph)[source]#

Topological sorting by depth first search

Parameters:: graph – directed graph in listlist format, cannot be listdict
Returns:: list of vertices in order
Complexity:: O(|V|+|E|)

tryalgo.tortoise_hare module#

Detect a cycle for a function on a finite domain.

jill-jenn vie et christoph durr - 2023

tryalgo.tortoise_hare.tortoise_hare(f, source=0)[source]#

Detect cycle for function f, starting from source

Parameters:

f – function from finite domain to itself
source – element in this domain

Warning:

if the function does not reach a cycle from source then this function loops forever

Returns:

c, d such that after d iterations of f a cycle is reached, which has period c

Complexity:

O(d+c)

tryalgo.trie module#

trie - correcteur orthographique

jill-jênn vie et christoph dürr - 2014-2019

tryalgo.trie.Trie(S)[source]#

Parameters:: S – set of words
Returns:: trie containing all words from S
Complexity:: linear in total word sizes from S

class tryalgo.trie.TrieNode[source]#: Bases: object

tryalgo.trie.add(T, w, i=0)[source]#

Parameters:

T – trie
w (string) – word to be added to T

Returns:

new trie consisting of w added into T

Complexity:

O(len(w))

tryalgo.trie.search(T, dist, w, i=0)[source]#: Searches for w[i:] in trie T with distance at most dist

tryalgo.trie.spell_check(T, w)[source]#

Spellchecker

Parameters:

T – trie encoding the dictionary
w – given word

Returns:

a closest word from the dictionary

Complexity:

linear if distance was constant

tryalgo.two_sat module#

Solving 2-SAT boolean formulas

jill-jenn vie et christoph durr - 2015-2019

tryalgo.two_sat.two_sat(formula)[source]#

Solving a 2-SAT boolean formula

Parameters:: formula – list of clauses, a clause is pair of literals over X1,…,Xn for some n. a literal is an integer, for example -1 = not X1, 3 = X3
Returns:: table with boolean assignment satisfying the formula or None
Complexity:: linear

tryalgo.union_rectangles module#

Union of rectangles

jill-jênn vie et christoph dürr - 2014-2019

class tryalgo.union_rectangles.CoverQuery(L)[source]#

Bases: object

Segment tree to maintain a set of integer intervals and permitting to query the size of their union.

change(i, k, offset)[source]#: when offset = +1, adds an interval [i, k], when offset = -1, removes it :complexity: O(log L)

cover()[source]#

Returns:: the size of the union of the stored intervals

tryalgo.union_rectangles.rectangles_contains_point(R, x, y)[source]#: Decides if at least one of the given rectangles contains a given point either strictly or on its left or top border

tryalgo.union_rectangles.union_intervals(intervals)[source]#

Size of the union of a set of intervals

Sweep from left to right. Maintain in a counter number of opened intervals minus number of closed intervals.

Parameters:: intervals – Counter, which describes a multiset of intervals. an interval is a pair of values.
Returns:: size of the union of those intervals
Complexity:: $O(n \log n)$

tryalgo.union_rectangles.union_rectangles(R)[source]#

Area of union of rectangles.

Sweep from top to bottom. Maintain in a set the horizontal projection of rectangles, for which the top border has been processed but not yet the bottom.

Parameters:: R – list of rectangles defined by (x1, y1, x2, y2) where (x1, y1) is top left corner and (x2, y2) bottom right corner
Returns:: area
Complexity:: $O(n^2 \log n)$

tryalgo.union_rectangles.union_rectangles_fast(R)[source]#

Area of union of rectangles

Parameters:: R – list of rectangles defined by (x1, y1, x2, y2) where (x1, y1) is top left corner and (x2, y2) bottom right corner
Returns:: area
Complexity:: $O(n^2)$

tryalgo.union_rectangles.union_rectangles_fastest(R)[source]#

Area of union of rectangles

Parameters:: R – list of rectangles defined by (x1, y1, x2, y2) where (x1, y1) is top left corner and (x2, y2) bottom right corner
Returns:: area
Complexity:: $O(n \log n)$

tryalgo.union_rectangles.union_rectangles_naive(R)[source]#

Area of union of rectangles

Parameters:: R – list of rectangles defined by (x1, y1, x2, y2) where (x1, y1) is top left corner and (x2, y2) bottom right corner
Returns:: area
Complexity:: $O(n^3)$

tryalgo.windows_k_distinct module#

All sliding windows containing k distinct elements

jill-jenn vie et christoph durr - 2014-2018

tryalgo.windows_k_distinct.windows_k_distinct(x, k)[source]#

Find all largest windows containing exactly k distinct elements

Parameters:

x – list or string
k – positive integer

Yields:

largest intervals [i, j) with len(set(x[i:j])) == k

Complexity:

O(|x|)