# tryalgo package¶

## tryalgo.anagrams module¶

tryalgo.anagrams.anagrams(w)[source]

group a list of words into anagrams

Parameters: w – list of strings list of lists $$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¶

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

Bezout coefficients for a and b

Parameters: a,b – non-negative integers O(log a + log b)
tryalgo.arithm.binom(n, k)[source]

Binomial coefficients for $$n \choose k$$

Parameters: n,k – non-negative integers O(k)
tryalgo.arithm.binom_modulo(n, k, p)[source]

Binomial coefficients for $$n \choose k$$, modulo p

Parameters: n,k – non-negative integers O(k)
tryalgo.arithm.inv(a, p)[source]

Inverse of a in $${\mathbb Z}_p$$

Parameters: a,p – non-negative integers O(log a + log p)
tryalgo.arithm.pgcd(a, b)[source]

Greatest common divisor for a and b

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

## tryalgo.arithm_expr_eval module¶

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

Evaluates a given expression

Parameters: expr – expression cell – dictionary variable name -> expression numerical value of expression linear
tryalgo.arithm_expr_eval.arithm_expr_parse(line)[source]

Constructs an arithmetic expression tree

Parameters: line – list of token strings containing the expression expression tree linear

## tryalgo.arithm_expr_target module¶

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¶

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 distance table, precedence table, bool bool is True if a negative circuit is reachable from the source, circuits can have length 2. O(|V|*|E|)

## tryalgo.bfs module¶

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 distance table, precedence table O(|V|+|E|)

## tryalgo.biconnected_components module¶

tryalgo.biconnected_components.cut_nodes_edges(graph)[source]

Bi-connected components

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

## tryalgo.bipartite_matching module¶

tryalgo.bipartite_matching.max_bipartite_matching(bigraph)[source]

Bipartie maximum matching

Parameters: bigraph – adjacency list, index = vertex in U, value = neighbor list in V U = V = {0, 1, 2, …, n - 1} for n = len(bigraph) matching list, match[v] == u iff (u, v) in matching 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 U and V can have different cardinalities matching list, match[v] == u iff (u, v) in matching O(|V|*|E|)

## tryalgo.bipartite_vertex_cover module¶

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 U = V = {0, 1, 2, …, n - 1} for n = len(bigraph) boolean table for U, boolean table for V 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 O(|V|*|E|)

## tryalgo.closest_points module¶

tryalgo.closest_points.closest_points(S)[source]

Closest pair of points

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

## tryalgo.closest_values module¶

tryalgo.closest_values.closest_values(L)[source]

Closest values

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

## tryalgo.convex_hull module¶

tryalgo.convex_hull.andrew(S)[source]

Convex hull by Andrew

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

## tryalgo.dfs module¶

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 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 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. 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. 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 precedence table 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 list of vertices in a cycle or None O(|V|+|E|)

## tryalgo.dijkstra module¶

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 weights are non-negative distance table, precedence table 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 weights are non-negatif and weights are infinite for non edges distance table, precedence table O(|V| + |E|log|V|)

## tryalgo.dilworth module¶

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 graph is acyclic table giving for each vertex the number of its chains same as matching

## tryalgo.dinic module¶

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 skew symmetric flow matrix, flow value $$O(|V|^2 |E|)$$

## tryalgo.dist_grid module¶

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 indices target ((int,int)) – exploration stops if target is reached linear in grid size

## tryalgo.edmonds_karp module¶

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 flow matrix, flow value $$O(|V|*|E|^2)$$

## tryalgo.eulerian_tour module¶

tryalgo.eulerian_tour.eulerian_tour_directed(graph)[source]

Eulerian tour on a directed graph

Parameters: graph – directed graph in listlist format, cannot be listdict graph is eulerian eulerian cycle as a vertex list 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 graph is eulerian eulerian cycle as a vertex list 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 test if tour is eulerian 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 undirected graph in listlist representation 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 nothing O(|V|^2 + |E|)

## tryalgo.fast_exponentiation module¶

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 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 O(log b)

## tryalgo.fenwick module¶

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

Bases: object

maintains a tree to allow quick updates and queries

add(i, val)[source]
Parameters: i (int) – positive adds val to t[i]
get(i)[source]

Parameters: i (int) – positive
intervalAdd(a, b, val)[source]

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

Parameters: a b (int) – with 1 <= a <= b
intervalSum(a, b)[source]
Parameters: a b (int) – with 1 <= a <= b t[a] + … + t[b]
prefixSum(i)[source]
Parameters: i (int) – non negative t[1] + … + t[i]

## tryalgo.floyd_warshall module¶

tryalgo.floyd_warshall.floyd_warshall(weight)[source]

All pairs shortest paths by Floyd-Warshall

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

## tryalgo.ford_fulkerson module¶

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 flow matrix, flow value O(|V|*|E|*max_capacity)

## tryalgo.freivalds module¶

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 False with high probability if AB != C $$O(n^2)$$

## tryalgo.gale_shapley module¶

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 matching table, from women to men $$O(n^2)$$

## tryalgo.gauss_jordan module¶

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

Linear equation system Ax=b by Gauss-Jordan

Parameters: A – n by m matrix x – table of size n b – table of size m x will contain solution if any 0 if no solution, 1 if solution unique, 2 otherwise $$O(n^2m)$$

## tryalgo.graph module¶

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 linear 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) linear 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 path from root to v, in form of a list 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 couple with listlist representation, and weight matrix 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 graph in listdict representation 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 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 linear 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 graph in listlist format, possibly followed by weight matrix 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 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 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 tree in predecessor table representation linear
tryalgo.graph.tree_prec_to_adj(prec, root=0)[source]

Transforms a tree given as predecessor table into adjacency list form

Parameters: prec – predecessor table representing a tree, prec[u] == v iff u is successor of v, except for the root where prec[root] == root root – root vertex of the tree undirected graph in listlist representation 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 O(|V| + |E|)

## tryalgo.graph01 module¶

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 distance table, predecessor table O(|V|+|E|)

## tryalgo.horn_sat module¶

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 and can be empty. posvar is the positive variable and can be None. Variables can be any hashable objects, as integers or strings for example. None if formula is not satisfiable, else a minimal set of variables that have to be set to true in order to satisfy the formula. 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¶

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

Extract Huffman code from a Huffman tree

Parameters: tree – a node of the tree prefix – a list with the 01 characters encoding the path from the root to the node tree O(n)
tryalgo.huffman.huffman(freq)[source]

Huffman code

Parameters: freq – dictionary with frequencies for each item dictionary with binary code string for each item O(n log n)

## tryalgo.interval_cover module¶

tryalgo.interval_cover.interval_cover(I)[source]

Minimum interval cover

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

## tryalgo.interval_tree module¶

tryalgo.interval_tree.interval_tree(intervals)[source]

Construct an interval tree

Parameters: intervals – list of half-open intervals encoded as value pairs [left, right) intervals are lexicographically ordered >>> assert intervals == sorted(intervals) the root of the interval tree $$O(n)$$
tryalgo.interval_tree.intervals_containing(t, p)[source]

Query the interval tree

Parameters: t – root of the interval tree p – value a list of intervals containing p 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¶

tryalgo.intervals_union.intervals_union(S)[source]

Union of intervals

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

## tryalgo.knapsack module¶

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 number of items non-zero value optimal solution, list of item indexes in solution 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 number of items non-zero value optimal solution, list of item indexes in solution O(n * cmax), for n = number of items

## tryalgo.knuth_morris_pratt module¶

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 index i such that s[i: i + len(t)] == t, or -1 O(len(s) + len(t))

## tryalgo.knuth_morris_pratt_border module¶

tryalgo.knuth_morris_pratt_border.maximum_border_length(w)[source]

Maximum string borders by Knuth-Morris-Pratt

Parameters: w – string table l such that l[i] is the longest border length of w[:i + 1] linear
tryalgo.knuth_morris_pratt_border.powerstring_by_border(u)[source]

Power string by Knuth-Morris-Pratt

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

## tryalgo.kruskal module¶

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

Bases: object

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

find(x)[source]
Returns: identifier of part containing x O(inverse_ackerman(n))
union(x, y)[source]

Merges part that contain x and part containing y

Returns: False if x, y are already in same part O(inverse_ackerman(n))
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 list of edges of the tree O(|E|log|E|)

## tryalgo.kuhn_munkres module¶

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. 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. matching table from U to V, value of matching $$O(|U|^2 |V|)$$

## tryalgo.kuhn_munkres_n4 module¶

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 $$O(n^4)$$

## tryalgo.laser_mirrors module¶

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

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 lists left and right. left[j] = the number of i tab[j]. right[i] = the number of i tab[j]. O(n log n)

## tryalgo.levenshtein module¶

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

Levenshtein edit distance

Parameters: x – y – strings distance O(|x|*|y|)

## tryalgo.longest_common_subsequence module¶

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

Longest common subsequence

Dynamic programming

Parameters: x – y – x, y are lists or strings longest common subsequence in form of a string O(|x|*|y|)

## tryalgo.longest_increasing_subsequence module¶

tryalgo.longest_increasing_subsequence.longest_increasing_subsequence(x)[source]

Longest increasing subsequence

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

## tryalgo.lowest_common_ancestor module¶

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

tryalgo.majority.majority(L)[source]

Majority

Parameters: L – list of elements element that appears most in L, tie breaking with smallest element $$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¶

tryalgo.manacher.manacher(s)[source]

Longest palindrome in a string by Manacher

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

## tryalgo.matrix_chain_mult module¶

tryalgo.matrix_chain_mult.matrix_chain_mult(M)[source]

Matrix chain multiplication

Parameters: M – list of matrices M[0] * … * M[-1], computed in time optimal order 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 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] $$O(n^2)$$

## tryalgo.max_interval_intersec module¶

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 O(n log n), where n = len(S)

## tryalgo.merge_ordered_lists module¶

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

Merge two ordered lists

Parameters: x – y – x,y are non decreasing ordered lists union of x and y in order linear

## tryalgo.min_mean_cycle module¶

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 cycle as vertex list, average arc weights or None if there is no cycle from start O(|V|*|E|)

## tryalgo.next_permutation module¶

tryalgo.next_permutation.convert(word, ass)[source]
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 table to next permutation False if permutation is already lexicographical maximal O(n)
tryalgo.next_permutation.solve_word_addition(S)[source]

## tryalgo.our_heap module¶

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¶

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.partition_refinement module¶

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¶

tryalgo.permutation_rank.permutation_rank(p)[source]

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

Parameters: p – list of length n containing all integers from 0 to n-1 rank between 0 and n! -1 computation with big numbers 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

Parameters: n (r) – integers with 0 ≤ r < n! permutation p as a list of n integers computation with big numbers O(n^2)

## tryalgo.polygon module¶

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] area 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 True if the segements do not intersect O(n log n) for n=len(polygon)

## tryalgo.pq_tree module¶

Solve the consecutive all ones column problem using PQ-trees

In short, a PQ-tree represents sets of total orders over a ground set. The leafs are the values of the ground set. Inner nodes are of type P or Q. P means all permutations of the children are allowed. Q means only the left to right or the right to left order of the children is allowed.

The method restrict(S), changes the tree such that it represents only total orders which would leave the elements of the set S consecutive. The complexity of restrict is linear in the tree size.

References:

https://courses.cs.washington.edu/courses/cse421/10au/lectures/PQ.pdf
http://www-math.mit.edu/~hajiagha/pp11.ps

Disclaimer: this implementation does not have the optimal time complexity. And also there are more recent and easier algorithms for this problem.

exception tryalgo.pq_tree.IsNotC1P[source]

Bases: Exception

The given instance does not have the all consecutive ones property

class tryalgo.pq_tree.PQ_node(shape, value=None)[source]

Bases: object

add(node)[source]

add_all(L)[source]
add_group(L)[source]

Add elements of L as descendants of the node. If there are several elements in L, group them in a P-node first

border(L)[source]

Append to L the border of the subtree.

class tryalgo.pq_tree.PQ_tree(universe)[source]

Bases: object

border()[source]

returns the list of the leafs in order

reduce(S)[source]
tryalgo.pq_tree.consecutive_ones_property(sets, universe=None)[source]

Check the consecutive ones property.

Parameters: sets (list) – is a list of subsets of the ground set. groundset – is the set of all elements, by default it is the union of the given sets returns a list of the ordered ground set where every given set is consecutive, or None if there is no solution. O(len(groundset) * len(sets)) an optimal implementation would have complexity O(len(groundset) + len(sets) + sum(map(len,sets))), and there are more recent easier algorithms for this problem.

## tryalgo.predictive_text module¶

tryalgo.predictive_text.predictive_text(dic)[source]

Predictive text for mobile phones

Parameters: dic – associates weights to words from [a-z]* a dictionary associating to words from [2-9]* a corresponding word from the dictionary with highest weight 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¶

tryalgo.primes.eratosthene(n)[source]

Prime numbers by sieve of Eratosthene

Parameters: n – positive integer n > 2 list of prime numbers
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 list of prime numbers, and list of prime factors O(n)

## tryalgo.rabin_karp module¶

tryalgo.rabin_karp.matches(s, t, i, j, k)[source]

tests if s[i:i + k] equals t[j:j + k]

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 (i, j) such that s[i:i + k] == t[j:j + k] or None. In case of tie, lexicographical minimum (i, j) is returned 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 index i such that s[i: i + len(t)] == t, or -1 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¶

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]} O(log len(t))

## tryalgo.rectangles_from_grid module¶

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 area, left, top, right, bottom of optimal rectangle consisting of all (i,j) with left <= j < right and top <= i <= bottom linear

## tryalgo.rectangles_from_histogram module¶

tryalgo.rectangles_from_histogram.rectangles_from_histogram(H)[source]

Largest Rectangular Area in a Histogram

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

## tryalgo.rectangles_from_points module¶

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 the number of rectangles $$O(n^2)$$

## tryalgo.roman_numbers module¶

tryalgo.roman_numbers.int2roman(val)[source]

Code roman number

Parameters: val – integer between 1 and 9999 the corresponding roman number 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 the decoded roman number linear (if that makes sense for constant bounded input size)

## tryalgo.scalar module¶

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

Permute vector to minimize scalar product

Parameters: x – y – x, y are vectors of same size min sum x[i] * y[sigma[i]] over all permutations sigma O(n log n)

## tryalgo.shortest_cycle module¶

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 None or a list C describing a shortest cycle O(|V|*|E|)
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. O(V^3)

## tryalgo.skip_list module¶

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]
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]
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¶

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 list of lists for each component linear
tryalgo.strongly_connected_components.tarjan(graph)[source]

Strongly connected components by Tarjan, iterative implementation

Parameters: graph – directed graph in listlist format, cannot be listdict list of lists for each component linear
tryalgo.strongly_connected_components.kosaraju(graph)[source]

Strongly connected components by Kosaraju

Parameters: graph – directed graph in listlist format, cannot be listdict list of lists for each component linear
tryalgo.strongly_connected_components.reverse(graph)[source]

replace all arcs (u, v) by arcs (v, u) in a graph

## tryalgo.subsetsum module¶

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

Coin change

Parameters: x – table of non negative values R – target value True if there is a non negative linear combination of x that has value R O(n*R)
tryalgo.subsetsum.subset_sum(x, R)[source]

Subsetsum

Parameters: x – table of non negative values R – target value True if a subset of x sums to R O(n*R)

## tryalgo.subsetsum_divide module¶

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

All subsetsums from x[i:]

Parameters: x – table of values i (int) – index defining suffix of x to be considered over all values, in arbitrary order $$O(2^{len(x)-i})$$
tryalgo.subsetsum_divide.subset_sum(x, R)[source]

Subsetsum by splitting

Parameters: x – table of values R – target value if there is a subsequence of x with total sum R $$O(n^{\lceil n/2 \rceil})$$

## tryalgo.sudoku module¶

tryalgo.sudoku.sudoku(G)[source]

Solving Sudoku

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

## tryalgo.three_partition module¶

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 triplet of the integers encoding the sets, or None otherwise $$O(2^{2n})$$

## tryalgo.topological_order module¶

tryalgo.topological_order.topological_order(graph)[source]

Topological sorting by maintaining indegree

Parameters: graph – directed graph in listlist format, cannot be listdict list of vertices in order 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 list of vertices in order O(|V|+|E|)

## tryalgo.trie module¶

tryalgo.trie.Trie(S)[source]
Parameters: S – set of words trie containing all words from S linear in total word sizes from S
class tryalgo.trie.Trie_Node[source]

Bases: object

tryalgo.trie.add(T, w, i=0)[source]
Parameters: T – trie w (string) – word to be added to T new trie consisting of w added into T 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 a closest word from the dictionary linear if distance was constant

## tryalgo.two_sat module¶

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 table with boolean assignment satisfying the formula or None linear

## tryalgo.union_rectangles module¶

class tryalgo.union_rectangles.Cover_query(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, delta)[source]

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

cover()[source]
Returns: the size of the union of the stored intervals
tryalgo.union_rectangles.union_rectangles(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 area $$O(n^2)$$

## tryalgo.windows_k_distinct module¶

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 largest intervals [i, j) with len(set(x[i:j])) == k O(|x|)

## Module contents¶

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