tryalgo package

Submodules

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

IPCELLS http://www.spoj.com/problems/IPCELLS/

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 :param x: allowed constants :param 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.bfs module

Breadth-first search, bfs and OurQueue christoph dürr - jill-jênn vie - 2015-2019

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

Assumption

U = V = {0, 1, 2, …, n - 1} for n = len(bigraph)

Returns

matching list, match[v] == u iff (u, v) in matching

Complexity

O(|V|*|E|)

tryalgo.bipartite_matching.max_bipartite_matching2(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.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='.')[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, i, j, mark='X', free='.')[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_iterative(graph, start, seen)[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, node, seen)[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, start=0)[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)[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.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.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-2020

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(graph, tour)[source]

Eulerian tour on an undirected graph

Parameters
  • graph – directed graph in listlist format, cannot be listdict

  • tour – vertex list

Returns

test 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
  • a b (int) – non negative

  • q (int) – positive

Complexity

O(log b)

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

Compute (a pow b) % q

Parameters
  • a b (int) – 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

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

intervalSum(a, b)[source]
Parameters

a b (int) – 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]

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.Graph[source]

Bases: object

add_arc(name_u, name_v, weight_uv=None)[source]
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

Parameters

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

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

x – string

Returns

largest k such that there is a string y with x = y^k

Complexity

O(len(x))

tryalgo.knuth_morris_pratt.powerstring_by_find(u)[source]

Power string using the python find method

Parameters

x – string

Returns

largest k such that there is a string y with x = y^k

Complexity

O(len(x))

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 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

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^2)\)

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

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

Find shortest simple cycle 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: tryalgo.skip_list.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: tryalgo.skip_list.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.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.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|)

Module contents

Tryalgo is a Python library of algorithms and data structures. It is implemented by Christoph Dürr (CNRS, Sorbonne Université, LIP6, Paris) and Jill-Jênn Vie (Inria, Lille) It is documented in the book “Programmation efficace, 128 Algorithmes qu’il faut avoir compris et codés en Python”, editor Ellipses.