Welcome to PyRival’s documentation!¶

Infinite Recursion¶

Infinite recursion can be achieved by using the pyrival.misc.bootstrap decorator

To use it you will need to make a few modifications to the recursive function:

Change all return to yield

Add yield before recursive function calls

For example the following code

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(10))   # prints 3628800
print(factorial(1000)) # exceeds recursion limit

will be changed to the following

import pyrival.misc

@pyrival.misc.bootstrap
def factorial(n):
    if n == 0:
        yield 1
    else:
        yield n * (yield factorial(n - 1))

print(factorial(10))    # prints 3628800
print(factorial(1000)   # prints 402387...000000
print(factorial(10000)) # prints 284625...000000

API Reference¶

pyrival.algebra¶

pyrival.algebra.chinese_remainder¶

pyrival.algebra.chinese_remainder.chinese_remainder(a, p)¶: returns x s.t. x = a[i] (mod p[i]) where p[i] is prime for all i

pyrival.algebra.chinese_remainder.composite_crt(b, m)¶: returns x s.t. x = a[i] (mod m[i]) for all i

pyrival.algebra.chinese_remainder.extended_gcd(a, b)¶: returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)

pyrival.algebra.chinese_remainder.gcd(x, y)¶: greatest common divisor of x and y

pyrival.algebra.discrete_log¶

pyrival.algebra.discrete_log.discrete_log(a, b, mod)¶: Returns smallest x > 0 s.t. pow(a, x, mod) == b or None if no such x exists. Note: works even if a and mod are not coprime.

pyrival.algebra.factors¶

pyrival.algebra.factors.all_factors(n)¶: returns a sorted list of all distinct factors of n

pyrival.algebra.factors.distinct_factors(n)¶: returns a list of all distinct factors of n

pyrival.algebra.factors.gcd(x, y)¶: greatest common divisor of x and y

pyrival.algebra.factors.memodict(f)¶: memoization decorator for a function taking a single argument

pyrival.algebra.factors.pollard_rho(n)¶: returns a random factor of n

pyrival.algebra.factors.prime_factors()¶: x.__getitem__(y) <==> x[y]

pyrival.algebra.fft¶

pyrival.algebra.fft.fft(a, inv=False)¶

pyrival.algebra.fft.fft_conv(a, b)¶

pyrival.algebra.fst¶

pyrival.algebra.fst.fst(a, oplus=<built-in function and_>, inv=False)¶

pyrival.algebra.fst.fst_conv(a, b)¶

pyrival.algebra.gcd¶

pyrival.algebra.gcd.extended_gcd(a, b)¶: returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)

pyrival.algebra.gcd.gcd(x, y)¶: greatest common divisor of x and y

pyrival.algebra.gcd.gcdm(*args)¶

pyrival.algebra.gcd.lcm(a, b)¶

pyrival.algebra.gcd.lcmm(*args)¶

pyrival.algebra.is_prime¶

pyrival.algebra.is_prime.is_prime(n)¶: returns True if n is prime else False

pyrival.algebra.mod_sqrt¶

pyrival.algebra.mod_sqrt.mod_sqrt(a, p)¶: returns x s.t. x**2 == a (mod p)

pyrival.algebra.modinv¶

pyrival.algebra.modinv.extended_gcd(a, b)¶: returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)

pyrival.algebra.modinv.modinv(a, m)¶: returns the modular inverse of a w.r.t. to m, works when a and m are coprime

pyrival.algebra.ntt¶

pyrival.algebra.ntt.fmod(a)¶

pyrival.algebra.ntt.fmul(a, b, c=0.0)¶

pyrival.algebra.ntt.fpow(x, y)¶

pyrival.algebra.ntt.fround(x)¶

pyrival.algebra.ntt.ntt(a, inv=False)¶

pyrival.algebra.ntt.ntt_conv(a, b)¶

pyrival.algebra.phi¶

pyrival.algebra.phi.phi(n)¶: returns phi(x) for all x <= n

pyrival.algebra.primitive_root¶

pyrival.algebra.primitive_root.gcd(x, y)¶: greatest common divisor of x and y

pyrival.algebra.primitive_root.ilog(n)¶: returns the smallest a, b s.t. a**b = n for integer a, b

pyrival.algebra.primitive_root.memodict(f)¶: memoization decorator for a function taking a single argument

pyrival.algebra.primitive_root.pollard_rho(n)¶: returns a random factor of n

pyrival.algebra.primitive_root.prime_factors()¶: x.__getitem__(y) <==> x[y]

pyrival.algebra.primitive_root.primitive_root(p)¶: returns a primitive root of p

pyrival.algebra.sieve¶

pyrival.algebra.sieve.prime_list(n)¶: returns a list of primes <= n

pyrival.algebra.sieve.prime_sieve(n)¶: returns a sieve of primes >= 5 and < n

pyrival.combinatorics¶

pyrival.combinatorics.combinatorics¶

pyrival.combinatorics.combinatorics.bell(n)¶

pyrival.combinatorics.combinatorics.catalan(n)¶

pyrival.combinatorics.combinatorics.derangements(n)¶

pyrival.combinatorics.combinatorics.euler(n, k)¶

pyrival.combinatorics.combinatorics.memoize(f)¶: memoization decorator for a function taking one or more arguments

pyrival.combinatorics.combinatorics.multinomial(k)¶

pyrival.combinatorics.combinatorics.nCr(n, r)¶

pyrival.combinatorics.combinatorics.stirling_2(n, k)¶

pyrival.combinatorics.nCr_mod¶

pyrival.combinatorics.nCr_mod.make_nCr_mod(max_n=200000, mod=1000000007)¶

pyrival.combinatorics.partitions¶

pyrival.combinatorics.partitions.memoize(f)¶: memoization decorator for a function taking one or more arguments

pyrival.data_structures¶

pyrival.data_structures.BitArray¶

class pyrival.data_structures.BitArray.BitArray(size)¶

Bases: object

implements bitarray using bytearray

pyrival.data_structures.CFraction¶

pyrival.data_structures.CFraction.CFrac2Frac(cfrac)¶

pyrival.data_structures.CFraction.CFraction(frac)¶

pyrival.data_structures.DisjointSetUnion¶

class pyrival.data_structures.DisjointSetUnion.DisjointSetUnion(n)¶

Bases: object

find(a)¶

set_size(a)¶

union(a, b)¶

class pyrival.data_structures.DisjointSetUnion.UnionFind(n)¶

Bases: object

find(a)¶

union(a, b)¶

pyrival.data_structures.FenwickTree¶

class pyrival.data_structures.FenwickTree.FenwickTree(x)¶

Bases: object

findkth(k)¶: Find largest idx such that sum(bit[:idx]) <= k

query(end)¶: calc sum(bit[:end])

update(idx, x)¶: updates bit[idx] += x

pyrival.data_structures.Fraction¶

class pyrival.data_structures.Fraction.Fraction(num=0, den=1)¶: Bases: object

pyrival.data_structures.Fraction.gcd(x, y)¶: greatest common divisor of x and y

pyrival.data_structures.Fraction.limit_denominator(frac, max_den=1000000)¶

pyrival.data_structures.Heap¶

class pyrival.data_structures.Heap.Heap(iterable=None, reverse=False)¶

Bases: object

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

replace(item)¶

class pyrival.data_structures.Heap.OrderHeap(iterable=None, key=<function OrderHeap.<lambda>>, reverse=False)¶

Bases: pyrival.data_structures.Heap.Heap

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

replace(item)¶

class pyrival.data_structures.Heap.RemovalHeap(iterable=None, reverse=False)¶

Bases: pyrival.data_structures.Heap.Heap

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

remove(item)¶

replace(item)¶

sweep()¶

class pyrival.data_structures.Heap.XHeap(iterable=None, key=<function XHeap.<lambda>>, reverse=False)¶

Bases: pyrival.data_structures.Heap.Heap

peek()¶

pop()¶

poppush(item)¶

push(item)¶

pushpop(item)¶

remove(item)¶

replace(item)¶

sweep()¶

pyrival.data_structures.LazySegmentTree¶

class pyrival.data_structures.LazySegmentTree.LazySegmentTree(data, default=0, func=<built-in function max>)¶

Bases: object

add(start, stop, value)¶: lazily add value to [start, stop)

query(start, stop, default=0)¶: func of data[start, stop)

pyrival.data_structures.LinkedList¶

class pyrival.data_structures.LinkedList.LinkedList(iterable=None)¶

Bases: object

append(value)¶

get_node(index)¶

insert(index, value)¶

insert_between(node, left_node, right_node)¶

class pyrival.data_structures.LinkedList.Node(value)¶: Bases: object

pyrival.data_structures.Node¶

class pyrival.data_structures.Node.Node(value)¶: Bases: object

pyrival.data_structures.PersistentSegTree¶

pyrival.data_structures.PersistentSegTree.create(n)¶: create a persistant segment tree of size n

pyrival.data_structures.PersistentSegTree.minimum(ind, l, r, n)¶: find mimimum of set[l:r] for segment tree ind, of size n

pyrival.data_structures.PersistentSegTree.setter(ind, i, val, n)¶: set set[i] = val for segment tree ind, of size n

pyrival.data_structures.RangeQuery¶

class pyrival.data_structures.RangeQuery.RangeQuery(data, func=<built-in function min>)¶

Bases: object

query(start, stop)¶: func of data[start, stop)

pyrival.data_structures.SegmentTree¶

class pyrival.data_structures.SegmentTree.SegmentTree(data, default=0, func=<built-in function max>)¶

Bases: object

query(start, stop)¶: func of data[start, stop)

pyrival.data_structures.SortedList¶

class pyrival.data_structures.SortedList.SortedList(iterable=[], _load=200)¶

Bases: object

add(value)¶: Add value to sorted list.

bisect_left(value)¶: Return the first index to insert value in the sorted list.

bisect_right(value)¶: Return the last index to insert value in the sorted list.

count(value)¶: Return number of occurrences of value in the sorted list.

discard(value)¶: Remove value from sorted list if it is a member.

pop(index=-1)¶: Remove and return value at index in sorted list.

remove(value)¶: Remove value from sorted list; value must be a member.

pyrival.data_structures.Treap¶

class pyrival.data_structures.Treap.TreapHashMap(data=None)¶

Bases: pyrival.data_structures.Treap.TreapMultiSet

add(key)¶

discard(key)¶

get(key, default=None)¶

remove(key)¶

class pyrival.data_structures.Treap.TreapHashSet(data=None)¶

Bases: pyrival.data_structures.Treap.TreapMultiSet

add(key)¶

discard(key)¶

remove(key)¶

class pyrival.data_structures.Treap.TreapMultiSet(data=None)¶

Bases: object

add(key)¶

ceiling(key)¶

discard(key)¶

floor(key)¶

higher(key)¶

lower(key)¶

max()¶

min()¶

remove(key)¶

root = 0¶

size = 0¶

class pyrival.data_structures.Treap.TreapSet(data=None)¶

Bases: pyrival.data_structures.Treap.TreapMultiSet

add(key)¶

pyrival.data_structures.Treap.treap_builder(sorted_data)¶: Build a treap in O(n) time using sorted data

pyrival.data_structures.Treap.treap_ceiling(root, key)¶

pyrival.data_structures.Treap.treap_create_node(key)¶

pyrival.data_structures.Treap.treap_erase(root, key)¶

pyrival.data_structures.Treap.treap_floor(root, key)¶

pyrival.data_structures.Treap.treap_higher(root, key)¶

pyrival.data_structures.Treap.treap_insert(root, key)¶

pyrival.data_structures.Treap.treap_insert_unique(root, key)¶

pyrival.data_structures.Treap.treap_lower(root, key)¶

pyrival.data_structures.Treap.treap_max(root)¶

pyrival.data_structures.Treap.treap_merge(left, right)¶

pyrival.data_structures.Treap.treap_min(root)¶

pyrival.data_structures.Treap.treap_split(root, key)¶

pyrival.data_structures.Trie¶

class pyrival.data_structures.Trie.Trie(*words)¶

Bases: object

add(word)¶

pyrival.data_structures.TwoSat¶

class pyrival.data_structures.TwoSat.TwoSat(n)¶

Bases: object

either(x, y)¶: either x or y must be True

set(x)¶: x must be True

solve()¶

pyrival.data_structures.TwoSat.scc(graph)¶: Finds what strongly connected components each node is a part of in a directed graph, it also finds a weak topological ordering of the nodes

pyrival.data_structures.convex_hull_trick¶

pyrival.data_structures.convex_hull_trick.convex_hull_trick(K, M, integer=True)¶

Given lines on the form y = K[i] * x + M[i] this function returns intervals, such that on each interval the convex hull is made up of a single line. Input:

K: list of the slopes M: list of the constants (value at x = 0) interger: boolean for turning on / off integer mode. Integer mode is exact, it

works by effectively flooring the seperators of the intervals.

Return:: hull_i: on interval j, line i = hull_i[j] is >= all other lines hull_x: interval j and j + 1 is separated by x = hull_x[j], (hull_x[j] is the last x in interval j)

pyrival.data_structures.convex_hull_trick.max_query(x, K, M, hull_i, hull_x)¶: Find maximum value at x in O(log n) time

pyrival.data_structures.tree_repr¶

pyrival.data_structures.tree_repr.tree_repr(tree)¶

pyrival.geometry¶

pyrival.geometry.convex_hull¶

pyrival.geometry.convex_hull.convex_hull(points)¶

pyrival.geometry.convex_hull.remove_middle(a, b, c)¶

pyrival.geometry.lines¶

pyrival.geometry.lines.collinear(p1, p2, p3)¶

pyrival.geometry.lines.dist(p1, p2)¶

pyrival.geometry.lines.gcd(x, y)¶: greatest common divisor of x and y

pyrival.geometry.lines.get_2dline(p1, p2)¶

pyrival.geometry.lines.get_line(p1, p2)¶

pyrival.geometry.lines.intersect(l1, l2)¶

pyrival.geometry.lines.is_parallel(l1, l2)¶

pyrival.geometry.lines.is_same(l1, l2)¶

pyrival.geometry.lines.rotate(p, theta, origin=(0, 0))¶

pyrival.geometry.polygons¶

pyrival.geometry.polygons.area(*p)¶

pyrival.geometry.polygons.circumcircle_radius(a, b, c)¶

pyrival.geometry.polygons.dist(p1, p2)¶

pyrival.geometry.polygons.incircle_radius(a, b, c)¶

pyrival.geometry.polygons.is_in_circle(p, c, r)¶

pyrival.geometry.polygons.perimeter(*p)¶

pyrival.geometry.vectors¶

pyrival.geometry.vectors.angle(oa, ob)¶

pyrival.geometry.vectors.closest_point(p, a, b, segment=False)¶

pyrival.geometry.vectors.cross2d(v1, v2)¶

pyrival.geometry.vectors.cross3d(v1, v2)¶

pyrival.geometry.vectors.dot(v1, v2)¶

pyrival.geometry.vectors.norm_sq(v)¶

pyrival.geometry.vectors.scale(v, s)¶

pyrival.geometry.vectors.to_vec(p1, p2)¶

pyrival.geometry.vectors.translate(p, v)¶

pyrival.graphs¶

pyrival.graphs.bellman_ford¶

pyrival.graphs.bellman_ford.bellman_ford(n, edges, start)¶

pyrival.graphs.bfs¶

pyrival.graphs.bfs.bfs(graph, start=0)¶

pyrival.graphs.bfs.layers(graph, start=0)¶

pyrival.graphs.components¶

pyrival.graphs.components.connected_components(n, graph)¶

pyrival.graphs.cycle_finding¶

pyrival.graphs.cycle_finding.cycle_finding(f, x0)¶

pyrival.graphs.dfs¶

pyrival.graphs.dfs.dfs(graph, start=0)¶

pyrival.graphs.dijkstra¶

pyrival.graphs.dijkstra.dijkstra(n, graph, start)¶: Uses Dijkstra’s algortihm to find the shortest path between in a graph.

pyrival.graphs.dinic¶

class pyrival.graphs.dinic.Dinic(n)¶

Bases: object

add_edge(a, b, c, rcap=0)¶

calc(s, t)¶

dfs(v, t, f)¶

pyrival.graphs.euler_walk¶

pyrival.graphs.euler_walk.euler_walk(n, adj)¶

pyrival.graphs.find_path¶

pyrival.graphs.find_path.find_path(start, end, parents)¶: Constructs a path between two vertices, given the parents of all vertices.

pyrival.graphs.floyd_warshall¶

pyrival.graphs.floyd_warshall.floyd_warshall(n, edges)¶

pyrival.graphs.hopcroft_karp¶

Produces a maximum cardinality matching of a bipartite graph

Example:

0—0

1—1

/

/

/

2 2

/

/

/

3

>>>> n = 4 >>>> m = 3 >>>> graph = [[0, 1], [1, 2], [1], [2]] >>>> match1, match2 = hopcroft_karp(graph, n, m) >>>> match1 [0, 1, -1, 2] >>>> match2 [0, 1, 3]

Meaning

0—0

1—1

2 2: /

/

/

3

pyrival.graphs.hopcroft_karp.hopcroft_karp(graph, n, m)¶: Maximum bipartite matching using Hopcroft-Karp algorithm, running in O(|E| sqrt(|V|))

pyrival.graphs.is_bipartite¶

pyrival.graphs.is_bipartite.is_bipartite(graph)¶

pyrival.graphs.kruskal¶

class pyrival.graphs.kruskal.UnionFind(n)¶

Bases: object

find(a)¶

merge(a, b)¶

pyrival.graphs.kruskal.kruskal(n, U, V, W)¶

pyrival.graphs.lca¶

class pyrival.graphs.lca.LCA(root, graph)¶: Bases: object

class pyrival.graphs.lca.RangeQuery(data, func=<built-in function min>)¶

Bases: object

query(begin, end)¶

pyrival.graphs.maximum_matching¶

pyrival.graphs.maximum_matching.maximum_matching(edges, mod=1073750017)¶

Returns the maximum cardinality matching of any simple graph (undirected, unweighted, no self-loops) Uses a randomized algorithm to compute the rank of the Tutte matrix The rank of the Tutte matrix is equal to twice the size of the maximum matching with high probability The probability for error is not more than n/mod

Complexity: O(n ^ 3) worst case, O(n * |matching_size|) on average

Parameters:	edges – a list of edges, assume nodes can be anything numbered from 0 to max number in edges mod – optional, a large random prime
Returns:	the maximum cardinality matching of the graph

pyrival.graphs.prim¶

pyrival.graphs.prim.prim(n, adj)¶

pyrival.graphs.scc¶

pyrival.graphs.scc.scc(graph)¶: Finds what strongly connected components each node is a part of in a directed graph, it also finds a weak topological ordering of the nodes

pyrival.graphs.toposort¶

pyrival.graphs.toposort.kahn(graph)¶

pyrival.graphs.toposort.toposort(graph)¶

pyrival.linear_algebra¶

pyrival.linear_algebra.matrix¶

pyrival.linear_algebra.matrix.eye(m)¶: returns an indentity matrix of order m

pyrival.linear_algebra.matrix.mat_add(*mat)¶

pyrival.linear_algebra.matrix.mat_inv(A)¶

pyrival.linear_algebra.matrix.mat_mul(A, B)¶

pyrival.linear_algebra.matrix.mat_pow(mat, power)¶: returns mat**power

pyrival.linear_algebra.matrix.mat_sub(A, B)¶

pyrival.linear_algebra.matrix.minor(mat, i, j)¶

pyrival.linear_algebra.matrix.transpose(mat)¶

pyrival.linear_algebra.matrix.vec_mul(mat, vec)¶

pyrival.linear_algebra.max_xor¶

Maximizes xor of values in a list (works with big integers)

Example: >>>> A = [10**20, 3, 6, 4] >>>> I = max_xor(A) >>>> xor = 0 >>>> for i in I: …. xor ^= A[i] …. >>>> xor 100000000000000000007

pyrival.linear_algebra.max_xor.max_xor(A)¶: Input: List A of non-negative integers Output: I such that xor(A[i] for i in I) is maximized

pyrival.linear_algebra.multivariable_crt¶

pyrival.linear_algebra.multivariable_crt.extended_gcd(a, b)¶: returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)

pyrival.linear_algebra.multivariable_crt.gcd(x, y)¶: greatest common divisor of x and y

pyrival.linear_algebra.multivariable_crt.is_sol(A, x, b, m)¶: checks if Ax = b mod m

pyrival.linear_algebra.multivariable_crt.mat_mul(A, B)¶

pyrival.linear_algebra.multivariable_crt.mat_sub(A, B)¶

pyrival.linear_algebra.multivariable_crt.mcrt(A, b, m)¶: returns x s.t. Ax = b mod m

pyrival.linear_algebra.multivariable_crt.modinv(a, m)¶: returns the modular inverse of a w.r.t. to m

pyrival.linear_algebra.multivariable_crt.pivot(A, m)¶: returns the pivot of A and m

pyrival.misc¶

pyrival.misc.FastIO¶

class pyrival.misc.FastIO.FastIO(file)¶

Bases: io.IOBase

flush()¶

Flush write buffers, if applicable.

This is not implemented for read-only and non-blocking streams.

newlines = 0¶

read()¶

readline()¶

Read and return a line from the stream.

If size is specified, at most size bytes will be read.

The line terminator is always b’n’ for binary files; for text files, the newlines argument to open can be used to select the line terminator(s) recognized.

class pyrival.misc.FastIO.IOWrapper(file)¶: Bases: io.IOBase

pyrival.misc.FastIO.input()¶

pyrival.misc.FastIO.str(x=b'')¶

pyrival.misc.Random¶

pyrival.misc.alphabeta¶

class pyrival.misc.alphabeta.AlphaBetaNode(value=None, children=None)¶: Bases: object

pyrival.misc.alphabeta.alphabeta(node, depth, alpha=-inf, beta=inf, maximizingPlayer=True)¶

pyrival.misc.as_integer_ratio¶

pyrival.misc.as_integer_ratio.as_integer_ratio(x, prec=53)¶

pyrival.misc.bit_hacks¶

pyrival.misc.bit_hacks.least_bit(x)¶

pyrival.misc.bit_hacks.next_mask(x)¶

pyrival.misc.bit_hacks.subset_masks(m)¶

pyrival.misc.bit_hacks.sum_of_subsets(K, D)¶

pyrival.misc.bootstrap¶

pyrival.misc.bootstrap.bootstrap(f, stack=[])¶

pyrival.misc.cumsum2d¶

pyrival.misc.cumsum2d.cumsum2d(A)¶

pyrival.misc.lis¶

pyrival.misc.lis.lis(nums, cmp=<function <lambda>>)¶

pyrival.misc.memoize¶

pyrival.misc.memoize.memodict(f)¶: Memoization decorator for a function taking a single argument.

pyrival.misc.memoize.memoize(f)¶: Memoization decorator for a function taking one or more arguments.

pyrival.misc.mod¶

pyrival.misc.order_statistic¶

pyrival.misc.order_statistic.order_statistic(a, k)¶: returns the k-th (0 <= k < len(a)) largest element of a

pyrival.misc.ordersort¶

pyrival.misc.ordersort.bucketsort(order, seq)¶

pyrival.misc.ordersort.long_ordersort(order, seq)¶

pyrival.misc.ordersort.multikey_ordersort(order, *seqs, sort=<function ordersort>)¶

pyrival.misc.ordersort.ordersort(order, seq, reverse=False)¶

pyrival.misc.ostream¶

class pyrival.misc.ostream.ostream¶: Bases: object

pyrival.misc.py3k¶

Python 3 compatibility tools.

pyrival.misc.readnumbers¶

pyrival.misc.readnumbers.readnumbers(zero=0)¶

pyrival.misc.split¶

pyrival.misc.split.split(b)¶

pyrival.numerical¶

pyrival.numerical.berlekamp_massey¶

pyrival.numerical.berlekamp_massey.berlekamp_massey(s)¶

pyrival.numerical.berlekamp_massey.linear_rec(S, tr, k)¶

pyrival.numerical.hill_climbing¶

pyrival.numerical.hill_climbing.hill_climbing(func, x_0, y_0, cmp=<built-in function min>)¶

pyrival.numerical.integrate¶

pyrival.numerical.integrate.fast_quad(func, a, b, eps=1e-06)¶

pyrival.numerical.integrate.quad(func, a, b, n=1000)¶

pyrival.numerical.integrate.rec(func, a, b, eps, S)¶

pyrival.numerical.integrate.simpson(func, a, b)¶

pyrival.numerical.interpolate¶

pyrival.numerical.interpolate.interpolate(points)¶

pyrival.numerical.iroot¶

pyrival.numerical.iroot.iroot(n, k=2)¶

pyrival.numerical.polynomial¶

pyrival.numerical.polynomial.diff(a)¶

pyrival.numerical.polynomial.divroot(a, x0)¶

pyrival.numerical.polynomial.poly(a, x)¶

pyrival.numerical.search¶

pyrival.numerical.search.binary_search(func, lo, hi, abs_prec=1e-07)¶: Locate the first value x s.t. func(x) = True within [lo, hi]

pyrival.numerical.search.discrete_binary_search(func, lo, hi)¶: Locate the first value x s.t. func(x) = True within [lo, hi]

pyrival.numerical.search.discrete_ternary_search(func, lo, hi)¶: Find the first maximum of unimodal function func() within [lo, hi]

pyrival.numerical.search.fractional_binary_search(func, lo=(0, 1), hi=(1, 0), limit=1000000)¶

pyrival.numerical.search.golden_section_search(a, b, func, abs_prec=1e-07)¶

pyrival.numerical.search.ternary_search(func, lo, hi, abs_prec=1e-07)¶: Find maximum of unimodal function func() within [lo, hi]

pyrival.strings¶

pyrival.strings.LCSubstr¶

pyrival.strings.LCSubstr.LCSubstr(a, b)¶

pyrival.strings.LPSubstr¶

pyrival.strings.LPSubstr.LPSubstr(s)¶

pyrival.strings.hashing¶

class pyrival.strings.hashing.Hashing(s, mod=2147483647, base1=1676490275, base2=1615721995)¶

Bases: object

get_hashes(length)¶

hashed(start, stop)¶

pyrival.strings.kmp¶

pyrival.strings.kmp.match(s, pat)¶

pyrival.strings.kmp.partial(s)¶

pyrival.strings.kmp.string_find(s, pat)¶

pyrival.strings.lcs¶

pyrival.strings.lcs.lcs(a, b)¶

pyrival.strings.lcs.lps(s)¶

pyrival.strings.min_rotation¶

pyrival.strings.min_rotation.least_rotation(s)¶

pyrival.strings.suffix_array¶

Calculates the suffix array and LCP array in O(n) time

Example: >>>> S = ‘cabbage’ >>>> SA = SAIS([ord(c) for c in S]) >>>> LCP = KASAI(S, SA) >>>> SA [1, 4, 3, 2, 0, 6, 5] >>>> LCP [1, 0, 1, 0, 0, 0]

pyrival.strings.suffix_array.KASAI(A, SA)¶: Calculates LCP array in O(n) time Input: String A and its suffix array SA

pyrival.strings.suffix_array.SAIS(A)¶: Calculates suffix array in O(len(A) + max(A)) Input: Int list A with A[i] >= 0 for all i

pyrival.tools¶

pyrival.tools.interactive_runner¶

pyrival.tools.interactive_runner.async_main(argv=['/home/docs/checkouts/readthedocs.org/user_builds/pyrival/envs/stable/bin/sphinx-build', '-T', '-b', 'readthedocssinglehtmllocalmedia', '-d', '_build/doctrees-readthedocssinglehtmllocalmedia', '-D', 'language=en', '.', '_build/localmedia'])¶

pyrival.tools.interactive_runner.main(argv=['/home/docs/checkouts/readthedocs.org/user_builds/pyrival/envs/stable/bin/sphinx-build', '-T', '-b', 'readthedocssinglehtmllocalmedia', '-d', '_build/doctrees-readthedocssinglehtmllocalmedia', '-D', 'language=en', '.', '_build/localmedia'])¶

pyrival.tools.interactive_runner.show_exit_code(process, prefix)¶

pyrival.tools.interactive_runner.tee(stream, streams, prefix)¶

pyrival.tools.stress_tester¶

pyrival.tools.stress_tester.cmd2func(args)¶

pyrival.tools.stress_tester.func2judge(sol)¶

pyrival.tools.stress_tester.stress_tester(tests, solution, judge=None, catch_all=False)¶