tryalgo package¶
Submodules¶
tryalgo.anagrams module¶
Anagrams christoph dürr - jill-jênn vie - 2013-2019
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_expr_eval module¶
Evaluate an arithmetic expression jill-jenn vie et christoph durr - 2014-2020
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.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.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
-
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) :param int lo: :param int hi: with hi >= lo :param float gap: :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
- 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_values module¶
Closest values jill-jênn vie et christoph dürr - 2014-2019
tryalgo.convex_hull module¶
Convex hull by Andrew jill-jênn vie et christoph dürr - 2014-2019
tryalgo.dancing_links module¶
Exact set cover by the dancing links algorithm jill-jenn vie et christoph durr - 2014-2018
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.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
- 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
- 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.dinic module¶
Maximum flow by Dinic jill-jênn vie et christoph dürr - 2015-2018
tryalgo.dist_grid module¶
Distances in a grid jill-jenn vie et christoph durr - 2014-2018 ——————————————–
tryalgo.edmonds_karp module¶
Maximum flow by Edmonds-Karp jill-jênn vie et christoph dürr - 2015-2019
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.fenwick module¶
Fenwick tree jill-jenn vie et christoph durr - 2014-2018
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.freivalds module¶
Test matrix product AB = C by Freivalds jill-jênn vie et christoph dürr - 2015-2020
tryalgo.gale_shapley module¶
Stable matching by Gale-Shapley jill-jênn vie et christoph durr - 2014-2019
tryalgo.gauss_jordan module¶
Linear equation system Ax=b by Gauss-Jordan jill-jenn vie et christoph durr - 2014-2018
tryalgo.graph module¶
Reading graphs from files and writing into files jill-jênn vie et christoph dürr - 2015-2019
-
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.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.interval_cover module¶
Minimum interval cover jill-jênn vie et christoph dürr - 2014-2020
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.intervals_union module¶
Union of intervals jill-jênn vie et christoph dürr - 2014-2019
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.kruskal module¶
Minimum spanning tree by kruskal jill-jenn vie et christoph durr - 2014-2018
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.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
-
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.longest_common_subsequence module¶
Longest increasing subsequence jill-jênn vie et christoph dürr - 2014-2019
tryalgo.longest_increasing_subsequence module¶
Longest increasing subsequence jill-jenn vie et christoph durr - 2014-2018
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
tryalgo.majority module¶
Majority jill-jenn vie et christoph durr - 2014-2019
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.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.merge_ordered_lists module¶
Merge two ordered lists jill-jênn vie et christoph dürr - 2014-2019
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.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
tryalgo.our_queue module¶
A FIFO queue christoph dürr - jill-jênn vie - 2015-2019
tryalgo.our_std module¶
Our Standards Jill-Jênn Vie et Christoph Dürr - 2020
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.
tryalgo.permutation_rank module¶
Permutation rank christoph dürr - 2016-2019
tryalgo.polygon module¶
Area of polygone mesures polygone jill-jenn vie et christoph durr - 2014-2018
tryalgo.predictive_text module¶
Predictive text for mobile phones jill-jenn vie et christoph durr and louis abraham - 2014-2019
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.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.
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_points module¶
How many rectangles can be formed from a set of points jill-jenn vie et christoph durr - 2014-2018
tryalgo.roman_numbers module¶
Evaluate an arithmetic expression jill-jênn vie et christoph dürr - 2014-2019
tryalgo.scalar module¶
Permute vector to minimize scalar product jill-jênn vie et christoph dürr - 2014-2019
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.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.
SortedDict
(iterable=())[source]¶
-
class
tryalgo.skip_list.
SortedSet
(iterable=())[source]¶
-
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.subsetsum module¶
subsetsum jill-jenn vie et christoph durr - 2015-2018
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.sudoku module¶
Solving Sudoku (nanpure) jill-jenn vie et christoph durr - 2014-2019
tryalgo.three_partition module¶
subsetsum jill-jênn vie et christoph dürr - 2015-2019
tryalgo.topological_order module¶
Topological order jill-jênn vie et christoph dürr - 2014-2019
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
-
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.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.
-
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.windows_k_distinct module¶
All sliding windows containing k distinct elements jill-jenn vie et christoph durr - 2014-2018
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.