tryalgo package¶
Submodules¶
tryalgo.anagrams module¶
tryalgo.arithm module¶

tryalgo.arithm.
bezout
(a, b)[source]¶ Bezout coefficients for a and b
Parameters: a,b – nonnegative integers Complexity: O(log a + log b)

tryalgo.arithm.
binom
(n, k)[source]¶ Binomial coefficients for \(n \choose k\)
Parameters: n,k – nonnegative integers Complexity: O(k)

tryalgo.arithm.
binom_modulo
(n, k, p)[source]¶ Binomial coefficients for \(n \choose k\), modulo p
Parameters: n,k – nonnegative integers Complexity: O(k)
tryalgo.arithm_expr_eval module¶
tryalgo.arithm_expr_target module¶
tryalgo.bellman_ford module¶

tryalgo.bellman_ford.
bellman_ford
(graph, weight, source=0)[source]¶ Single source shortest paths by BellmanFord
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¶
tryalgo.biconnected_components module¶

tryalgo.biconnected_components.
cut_nodes_edges
(graph)[source]¶ Biconnected components
Parameters: graph – undirected graph. in listlist format. Cannot be in listdict format. Returns: a tuple with the list of cutnodes and the list of cutedges Complexity: O(V+E)

tryalgo.biconnected_components.
cut_nodes_edges2
(graph)[source]¶ Biconnected 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 cutnodes and the list of cutedges Complexity: O(V+E) in average, O(V+E^2) in worst case due to use of dictionary
tryalgo.binary_search module¶

tryalgo.binary_search.
discrete_binary_search
(tab, lo, hi)[source]¶ Binary search in a table
Parameters:  tab – boolean monotone table with tab[hi] = True
 lo (int) –
 hi (int) – with hi >= lo
Returns: first index i in [lo,hi] such that tab[i]
Complexity: O(log(hilo))

tryalgo.binary_search.
continuous_binary_search
(f, lo, hi, gap=0.0001)[source]¶ Binary search for a function
Parameters:  f – boolean monotone function with f(hi) = True
 lo (int) –
 hi (int) – with hi >= lo
 gap (float) –
Returns: first value x in [lo,hi] such that f(x), x is computed up to some precision
Complexity: O(log((hilo)/gap))

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.
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.
ternary_search
(f, lo, hi, gap=1e10)[source]¶ Ternary maximum search for a bitonic function
Parameters:  f – boolean bitonic function (increasing then decreasing, not necessarily strictly)
 lo (int) –
 hi (int) – with hi >= lo
 gap (float) –
Returns: value x in [lo,hi] maximizing f(x), x is computed up to some precision
Complexity: O(log((hilo)/gap))
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 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¶

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¶
tryalgo.closest_values module¶
tryalgo.convex_hull module¶
tryalgo.dancing_links module¶
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, 4neighborhood
 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, 4neighborhood
 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 (booleantable) – 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 (booleantable) – will be set true for the connected component containing node.
Complexity: 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
Assumes: weights are nonnegative
Returns: distance table, precedence table
Complexity: O(V + ElogV)

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 nonnegatif and weights are infinite for non edges
Returns: distance table, precedence table
Complexity: O(V + ElogV)
tryalgo.dilworth module¶
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
Returns: skew symmetric flow matrix, flow value
Complexity: \(O(V^2 E)\)
tryalgo.dist_grid module¶
tryalgo.edmonds_karp module¶

tryalgo.edmonds_karp.
edmonds_karp
(graph, capacity, source, target)[source]¶ Maximum flow by EdmondsKarp
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¶

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¶
tryalgo.fenwick module¶
tryalgo.floyd_warshall module¶
tryalgo.ford_fulkerson module¶

tryalgo.ford_fulkerson.
ford_fulkerson
(graph, capacity, s, t)[source]¶ Maximum flow by FordFulkerson
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¶
tryalgo.gale_shapley module¶
tryalgo.gauss_jordan module¶
tryalgo.graph module¶

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 dictdict graph representation into a adjacency dictionary representation (listdict)
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 n1. Line for unweighted edge u,v contains two integers u, v. Line for weighted edge u,v contains three integers u, v, w[u,v].
 directed – true for a directed graph, false for undirected
 weighted – true for an edge weighted graph
Returns: graph in listlist format, possibly followed by weight matrix
Complexity: O(n + m) for unweighted graph, \(O(n^2)\) for weighted graph

tryalgo.graph.
readtab
(fi, ty)[source]¶  Reads a line from file with a space separated list
 of items of type ty
Parameters:  file – input stream, for example sys.stdin
 ty – a type, for example int
Returns: a tuple with elements of type ty

tryalgo.graph.
readval
(file, ty)[source]¶ Reads a line from file with an item of type ty
Parameters:  file – input stream, for example sys.stdin
 ty – a type, for example int
Returns: an element of type ty

tryalgo.graph.
tree_adj_to_prec
(graph, root=0)[source]¶ Transforms a tree given as adjacency list into predecessor table form. if graph is not a tree: will return a DFS spanning tree
Parameters: graph – directed graph in listlist or listdict format Returns: tree in predecessor table representation Complexity: linear

tryalgo.graph.
tree_prec_to_adj
(prec, root=0)[source]¶ Transforms a tree given as predecessor table into adjacency list form
Parameters:  prec – predecessor table representing a tree, prec[u] == v iff u is successor of v, except for the root where prec[root] == root
 root – root vertex of the tree
Returns: undirected graph in listlist representation
Complexity: linear

tryalgo.graph.
write_graph
(dotfile, graph, directed=False, node_label=None, arc_label=None, comment='', node_mark={}, arc_mark={})[source]¶ Writes a graph to a file in the DOT format
Parameters:  dotfile – the filename.
 graph – directed graph in listlist or listdict format
 directed – true if graph is directed, false if undirected
 weight – in matrix format or same listdict graph or None
 node_label – vertex label table or None
 arc_label – arc label matrix or None
 comment – comment string for the dot file or None
 node_mark – set of nodes to be shown in gray
 arc_marc – set of arcs to be shown in red
Complexity: O(V + E)
tryalgo.graph01 module¶

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¶
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. Returns: 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. Complexity: linear
tryalgo.huffman module¶
tryalgo.interval_cover module¶
tryalgo.interval_tree module¶

tryalgo.interval_tree.
interval_tree
(intervals)[source]¶ Construct an interval tree
Parameters: intervals – list of halfopen 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¶
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
Requires: number of items nonzero
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 nonzero
Returns: value optimal solution, list of item indexes in solution
Complexity: O(n * cmax), for n = number of items
tryalgo.knuth_morris_pratt module¶
tryalgo.knuth_morris_pratt_border module¶
tryalgo.kruskal module¶
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
primaldual algorithm:
Start with trivial solution l for dual and with trivial nonsolution x for primal.
Iteratively improve primal or dual solution, maintaining complementary slackness conditions.

tryalgo.kuhn_munkres.
kuhn_munkres
(G, TOLERANCE=1e06)[source]¶ Maximum profit bipartite matching by KuhnMunkres
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 bipartite 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¶
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.
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¶

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¶
tryalgo.longest_common_subsequence module¶
tryalgo.longest_increasing_subsequence module¶
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
tryalgo.majority module¶
tryalgo.manacher module¶
tryalgo.matrix_chain_mult module¶

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

class
tryalgo.partition_refinement.
PartitionRefinement
(n)[source]¶ Bases:
object
This data structure implements an order preserving partition with refinements.
tryalgo.permutation_rank module¶

tryalgo.permutation_rank.
permutation_rank
(p)[source]¶ Given a permutation of {0,..,n1} find its rank according to lexicographical order
Parameters: p – list of length n containing all integers from 0 to n1 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,..,n1} with rank according to lexicographical order equal to r
Parameters: n (r) – 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¶
tryalgo.pq_tree module¶
Solve the consecutive all ones column problem using PQtrees
In short, a PQtree 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:
[W] https://en.wikipedia.org/wiki/PQ_tree
 [L10] Richard Ladner, slides.
 https://courses.cs.washington.edu/courses/cse421/10au/lectures/PQ.pdf
 [H00] Mohammad Taghi Hajiaghayi, notes.
 http://wwwmath.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

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: returns a list of the ordered ground set where every given set is consecutive, or None if there is no solution.
Complexity: O(len(groundset) * len(sets))
Disclaimer: 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.primes module¶

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

tryalgo.rabin_karp.
rabin_karp_factor
(s, t, k)[source]¶ Find a common factor by RabinKarp
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¶

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¶

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¶
tryalgo.rectangles_from_points module¶
tryalgo.roman_numbers module¶
tryalgo.scalar module¶
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 Returns: None or a list C describing a shortest cycle Complexity: O(V*E)

tryalgo.shortest_cycle.
powergraph
(graph, k)[source]¶  Compute the kth 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 – nonnegative integer.
Complexity: O(V^3)
tryalgo.skip_list module¶

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¶

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.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.subsetsum module¶
tryalgo.subsetsum_divide module¶
tryalgo.sudoku module¶
tryalgo.three_partition module¶
tryalgo.topological_order module¶
tryalgo.trie module¶

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¶

tryalgo.two_sat.
two_sat
(formula)[source]¶ Solving a 2SAT 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¶
tryalgo.windows_k_distinct module¶
Module contents¶
Tryalgo is a python library of algorithms and data structures is implemented by Christoph Dürr (CNRS, UPMC, Paris 6) and JillJênn Vie (Université ParisSud). It is documented in the book “Programmation efficace, 128 Algorithmes qu’il faut avoir compris et codés en Python”, editor Ellipses.