Table of Contents
Introduction
There are several functions, objects, patterns and data structures to use when designing algorithms. I’ve created a list of “tools” to get reminded/inspired by when you want to design an algorithm. These are in random order.
Overview
| Tool / Module | Purpose in Algorithm Design | Official Docs |
|---|---|---|
itertools | High‑performance iterator building blocks: combinatorics, infinite iterators, filters, grouping, slicing. | Official documentation page |
functools | Higher‑order functions, memoization (lru_cache), partial application, comparison helpers. | Official documentation page |
collections | Specialized containers: deque (fast queues), Counter, defaultdict, namedtuple, ChainMap. | Official documentation page |
heapq | Heap‑based priority queue algorithms (min‑heap). | Official documentation page |
bisect | Binary search and sorted list insertion. | Official documentation page |
math | Mathematical functions, constants, factorial, gcd, trigonometry. | Official documentation page |
statistics | Descriptive statistics: mean, median, stdev, variance. | Official documentation page |
random | Random number generation, sampling, shuffling. | Official documentation page |
graphlib | Topological sorting for DAGs. | Official documentation page |
array | Space‑efficient typed arrays for numeric data. | Official documentation page |
queue | Thread‑safe FIFO, LIFO, and priority queues. | Official documentation page |
time / timeit | Timing, benchmarking, performance measurement. | Official documentation page Official documentation page |
operator | Functional interface to Python’s operators (for sorting keys, mapping, etc.). | Official documentation page |
re | Regular expressions for pattern matching and text parsing. | Official documentation page |
| Built‑in Functions | Core tools like sorted, enumerate, zip, map, filter, any, all, sum, min, max. | Official documentation page |
| Built‑in Data Structures | list, tuple, dict, set, frozenset, range, str — each with algorithm‑friendly methods. | Official documentation page Official documentation page |
Core
| Function | Description |
|---|---|
len() | Get the number of elements in a sequence or collection. |
range() | Generate sequences of integers, for loops, or iteration patterns. |
enumerate() | Loop with both index and value. |
zip() | Pair up elements from multiple iterables. Great for parallel iteration. |
sorted() | Return a sorted list from any iterable. Can take key functions for custom order. |
min() / max() | Quickly find minimum/maximum, optionally with a key function. |
sum() | Efficiently sum numeric iterables. |
map() / filter() | Functional style transformations and filtering. |
any() / all() | Test aggregate truthiness (Short‑circuit checks). |
(For a complete list of built-in functions for Python3).
Itertools
Infinite Iterators
| Function / Iterator | Example |
|---|---|
count() | count(10) → 10 11 12 13 14 ... |
cycle() | cycle('ABCD') → A B C D A B C D ... |
repeat() | repeat(10, 3) → 10 10 10 |
Iterators terminating on the shortest input sequence
| Function / Iterator | Example |
|---|---|
accumulate() | accumulate([1,2,3,4,5]) → 1 3 6 10 15 |
batched() | batched('ABCDEFG', n=2) → AB CD EF G |
chain() | chain('ABC', 'DEF') → A B C D E F |
chain.from_iterable() | chain.from_iterable(['ABC', 'DEF']) → A B C D E F |
compress() | compress('ABCDEF', [1,0,1,0,1,1]) → A C E F |
dropwhile() | dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8 |
filterfalse() | filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8 |
groupby() | groupby(['A','B','DEF'], len) → (1, A B) (3, DEF) |
islice() | islice('ABCDEFG', 2, None) → C D E F G |
pairwise() | pairwise('ABCDEFG') → AB BC CD DE EF FG |
starmap() | starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000 |
takewhile() | takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4 |
tee() | |
zip_longest() | zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D- |
Combinatoric Iterators
| Function / Iterator | Results |
|---|---|
product() | cartesian product, equivalent to a nested for-loop |
permutations() | r-length tuples, all possible orderings, no repeated elements |
combinations() | r-length tuples, in sorted order, no repeated elements |
combinations_with_replacement() | r-length tuples, in sorted order, with repeated elements |
Functools
| Function | Description |
|---|---|
cache(user_function) | Simple, lightweight, unbounded function cache (memoization). Equivalent to lru_cache(maxsize=None). |
cached_property(func) | Decorator that turns a method into a property computed once per instance and then cached. |
cmp_to_key(func) | Converts an old-style comparison function to a key function for sorting. |
lru_cache(user_function) lru_cache(maxsize=128, typed=False) | Decorator for least-recently-used caching of function results. |
total_ordering(cls) | Class decorator that fills in missing rich comparison methods based on one or more defined ones. |
partial(func, /, *args, **keywords) | Returns a new callable with some arguments pre-filled. |
partialmethod(func, /, *args, **keywords) | Like partial(), but designed for use with methods in classes. |
reduce(function, iterable[, initial]) | Applies a binary function cumulatively to items of an iterable, reducing it to a single value. |
singledispatch(func) | Turns a function into a single-dispatch generic function, allowing type-based overloading on the first argument. |
singledispatchmethod(func) | Like singledispatch(), but for methods; dispatches on the first non-self/cls argument. |
update_wrapper(wrapper, wrapped, assigned=WRAPPER_ASSIGNMENTS, updated=WRAPPER_UPDATES) | Updates a wrapper function to look like the wrapped function (metadata, attributes). |
wraps(wrapped, assigned=WRAPPER_ASSIGNMENTS, updated=WRAPPER_UPDATES) | Convenience decorator for update_wrapper() when defining wrapper functions. |
Collections
| Function | Description |
|---|---|
namedtuple() | factory function for creating tuple subclasses with named fields |
deque | list-like container with fast appends and pops on either end |
ChainMap | dict-like class for creating a single view of multiple mappings |
Counter | dict subclass for counting hashable objects |
OrderedDict | dict subclass that remembers the order entries were added |
defaultdict | dict subclass that calls a factory function to supply missing values |
UserDict | wrapper around dictionary objects for easier dict subclassing |
UserList | wrapper around list objects for easier list subclassing |
UserString | wrapper around string objects for easier string subclassing |
Heapq
| Function | Description |
|---|---|
heapq.heappush(heap, item) | Pushes item onto heap while maintaining the heap invariant. |
heapq.heappop(heap) | Pops and returns the smallest item from heap, maintaining the heap invariant. |
heapq.heappushpop(heap, item) | Pushes item onto heap, then pops and returns the smallest item — faster than separate push and pop calls. |
heapq.heapify(x) | Transforms list x into a valid heap in-place, in linear time. |
heapq.heapreplace(heap, item) | Pops and returns the smallest item, then pushes item onto heap — heap size stays the same. |
heapq.merge(*iterables, key=None, reverse=False) | Lazily merges multiple sorted inputs into a single sorted output iterator. |
heapq.nlargest(n, iterable, key=None) | Returns a list of the n largest elements from iterable. |
heapq.nsmallest(n, iterable, key=None) | Returns a list of the n smallest elements from iterable. |
Bisect
| Function | Description |
|---|---|
bisect_left(a, x, lo=0, hi=len(a), *, key=None) | Finds the insertion point for x in a to maintain sorted order, placing it before any existing equal elements. |
bisect_right(a, x, lo=0, hi=len(a), *, key=None) / bisect(...) | Like bisect_left(), but places the insertion point after any existing equal elements. |
insort_left(a, x, lo=0, hi=len(a), *, key=None) | Inserts x into a in sorted order, before any existing equal elements. |
insort_right(a, x, lo=0, hi=len(a), *, key=None) / insort(...) | Inserts x into a in sorted order, after any existing equal elements. |
Math
| Function | Description |
|---|---|
| Number-theoretic functions | |
comb(n, k) | Number of ways to choose k items from n items without repetition and without order |
factorial(n) | n factorial |
gcd(*integers) | Greatest common divisor of the integer arguments |
isqrt(n) | Integer square root of a nonnegative integer n |
lcm(*integers) | Least common multiple of the integer arguments |
perm(n, k) | Number of ways to choose k items from n items without repetition and with order |
| Floating point arithmetic | |
ceil(x) | Ceiling of x, the smallest integer greater than or equal to x |
fabs(x) | Absolute value of x |
floor(x) | Floor of x, the largest integer less than or equal to x |
fma(x, y, z) | Fused multiply-add operation: (x * y) + z |
fmod(x, y) | Remainder of division x / y |
modf(x) | Fractional and integer parts of x |
remainder(x, y) | Remainder of x with respect to y |
trunc(x) | Integer part of x |
| Floating point manipulation functions | |
copysign(x, y) | Magnitude (absolute value) of x with the sign of y |
frexp(x) | Mantissa and exponent of x |
isclose(a, b, rel_tol, abs_tol) | Check if the values a and b are close to each other |
isfinite(x) | Check if x is neither an infinity nor a NaN |
isinf(x) | Check if x is a positive or negative infinity |
isnan(x) | Check if x is a NaN (not a number) |
ldexp(x, i) | x * (2**i), inverse of function frexp() |
nextafter(x, y, steps) | Floating-point value steps steps after x towards y |
ulp(x) | Value of the least significant bit of x |
| Power, exponential and logarithmic functions | |
cbrt(x) | Cube root of x |
exp(x) | e raised to the power x |
exp2(x) | 2 raised to the power x |
expm1(x) | e raised to the power x, minus 1 |
log(x, base) | Logarithm of x to the given base (e by default) |
log1p(x) | Natural logarithm of 1+x (base e) |
log2(x) | Base-2 logarithm of x |
log10(x) | Base-10 logarithm of x |
pow(x, y) | x raised to the power y |
sqrt(x) | Square root of x |
| Summation and product functions | |
dist(p, q) | Euclidean distance between two points p and q given as an iterable of coordinates |
fsum(iterable) | Sum of values in the input iterable |
hypot(*coordinates) | Euclidean norm of an iterable of coordinates |
prod(iterable, start) | Product of elements in the input iterable with a start value |
sumprod(p, q) | Sum of products from two iterables p and q |
| Angular conversion | |
degrees(x) | Convert angle x from radians to degrees |
radians(x) | Convert angle x from degrees to radians |
| Trigonometric functions | |
acos(x) | Arc cosine of x |
asin(x) | Arc sine of x |
atan(x) | Arc tangent of x |
atan2(y, x) | atan(y / x) |
cos(x) | Cosine of x |
sin(x) | Sine of x |
tan(x) | Tangent of x |
| Hyperbolic functions | |
acosh(x) | Inverse hyperbolic cosine of x |
asinh(x) | Inverse hyperbolic sine of x |
atanh(x) | Inverse hyperbolic tangent of x |
cosh(x) | Hyperbolic cosine of x |
sinh(x) | Hyperbolic sine of x |
tanh(x) | Hyperbolic tangent of x |
| Special functions | |
erf(x) | Error function at x |
erfc(x) | Complementary error function at x |
gamma(x) | Gamma function at x |
lgamma(x) | Natural logarithm of the absolute value of the Gamma function at x |
| Constants | |
pi | π = 3.141592… |
e | e = 2.718281… |
tau | τ = 2π = 6.283185… |
inf | Positive infinity |
nan | “Not a number” (NaN) |
Statistics
Averages and measures of central location
| Function | Description |
|---|---|
mean() | Arithmetic mean (“average”) of data. |
fmean() | Fast, floating-point arithmetic mean, with optional weighting. |
geometric_mean() | Geometric mean of data. |
harmonic_mean() | Harmonic mean of data. |
kde() | Estimate the probability density distribution of the data. |
kde_random() | Random sampling from the PDF generated by kde(). |
median() | Median (middle value) of data. |
median_low() | Low median of data. |
median_high() | High median of data. |
median_grouped() | Median (50th percentile) of grouped data. |
mode() | Single mode (most common value) of discrete or nominal data. |
multimode() | List of modes (most common values) of discrete or nominal data. |
quantiles() | Divide data into intervals with equal probability. |
Measures of spread
| Function | Description |
|---|---|
pstdev() | Population standard deviation of data. |
pvariance() | Population variance of data. |
stdev() | Sample standard deviation of data. |
variance() | Sample variance of data. |
Statistics for relations between two inputs
| Function | Description |
|---|---|
covariance() | Sample covariance for two variables. |
correlation() | Pearson and Spearman’s correlation coefficients. |
linear_regression() | Slope and intercept for simple linear regression. |
Strings
| Function | Description |
|---|---|
len(s) | Returns the length (number of characters) of string s. |
str(obj) | Converts an object to its string representation. |
repr(obj) | Returns a developer‑friendly string representation (often with quotes/escapes). |
.lower() | Returns a lowercase version of the string. |
.upper() | Returns an uppercase version of the string. |
.casefold() | Aggressive lowercasing for caseless matching. |
.capitalize() | Capitalizes the first character, lowercases the rest. |
.title() | Capitalizes the first letter of each word. |
.swapcase() | Swaps uppercase to lowercase and vice versa. |
.istitle() | Checks if string is in title case. |
.islower() | Checks if all cased characters are lowercase. |
.isupper() | Checks if all cased characters are uppercase. |
.isalpha() | Checks if all characters are alphabetic. |
.isalnum() | Checks if all characters are alphanumeric. |
.isdecimal() | Checks if all characters are decimal characters. |
.isdigit() | Checks if all characters are digits. |
.isnumeric() | Checks if all characters are numeric characters. |
.isidentifier() | Checks if string is a valid Python identifier. |
.isprintable() | Checks if all characters are printable or string is empty. |
.isspace() | Checks if all characters are whitespace. |
.find(sub) / .rfind(sub) | Returns lowest/highest index of substring, or ‑1 if not found. |
.index(sub) / .rindex(sub) | Like find, but raises ValueError if not found. |
.count(sub) | Counts non‑overlapping occurrences of substring. |
.startswith(prefix) | Checks if string starts with prefix. |
.endswith(suffix) | Checks if string ends with suffix. |
.replace(old, new[, count]) | Returns a copy with old replaced by new. |
.strip([chars]) / .lstrip() / .rstrip() | Remove leading/trailing characters (default: whitespace). |
.split([sep[, maxsplit]]) / .rsplit() | Split into a list by separator. |
.splitlines([keepends]) | Split at line breaks. |
.join(iterable) | Join elements with the string as a separator. |
.format(*args, **kwargs) | Format string with placeholders {}. |
.format_map(mapping) | Like .format() but uses mapping directly. |
.expandtabs(tabsize=8) | Replace tabs with spaces. |
.zfill(width) | Pad string on the left with zeros to given width. |
.center(width[, fillchar]) | Center align with optional fill character. |
.ljust(width[, fillchar]) / .rjust(width[, fillchar]) | Left/right align. |
.encode(encoding="utf-8") | Encode string to bytes. |
.translate(table) | Apply character mapping table. |
.maketrans(x, y[, z]) | Create mapping table for .translate(). |
string.ascii_letters | Constant: lowercase + uppercase ASCII letters. |
string.ascii_lowercase | Constant: lowercase ASCII letters. |
string.ascii_uppercase | Constant: uppercase ASCII letters. |
string.digits | Constant: '0123456789'. |
string.hexdigits | Constant: Hexadecimal digits. |
string.octdigits | Constant: Octal digits. |
string.punctuation | Constant: All ASCII punctuation chars. |
string.printable | Constant: Digits, letters, punctuation, whitespace. |
string.whitespace | Constant: All ASCII whitespace chars. |
string.capwords(s, sep=None) | Capitalizes each word in s. |
string.Formatter | Class for customizable {} string formatting. |
string.Template | $placeholder string substitution class. |
re.search(pattern, s) | Regex search for first match in s. |
re.findall(pattern, s) | Return all matches of regex in s. |
re.sub(pattern, repl, s) | Replace regex matches with repl. |
textwrap.fill(s, width) | Wrap text to given width. |
ord(ch) / chr(code) | Unicode code point ⇄ character conversion |
Random
| Function | Description |
|---|---|
| Bookkeeping | |
seed(a=None, version=2) | Initialize the random number generator with a seed. |
getstate() | Return the current internal state of the generator. |
setstate(state) | Restore the generator’s state from a previous getstate() call. |
| Bytes | |
randbytes(n) | Return n random bytes (not for cryptographic use). |
| Integers | |
randrange(start, stop[, step]) | Return a randomly selected element from the given range. |
randint(a, b) | Return a random integer N such that a <= N <= b. |
getrandbits(k) | Return an integer with k random bits. |
| Sequences | |
choice(seq) | Return a random element from a non-empty sequence. |
choices(population, weights=None, *, cum_weights=None, k=1) | Return a list of k elements chosen with replacement, optionally weighted. |
shuffle(x) | Shuffle a sequence in place. |
sample(population, k, *, counts=None) | Return k unique elements chosen without replacement. |
| Discrete Distributions | |
binomialvariate(n=1, p=0.5) | Return number of successes in n trials with success probability p. |
| Real-valued Distributions | |
random() | Return a float in the range [0.0, 1.0). |
uniform(a, b) | Return a float N such that a <= N <= b (or reversed if b < a). |
triangular(low, high, mode) | Return a float between low and high with a given mode. |
betavariate(alpha, beta) | Beta distribution in range [0, 1]. |
expovariate(lambd=1.0) | Exponential distribution with rate parameter lambd. |
gammavariate(alpha, beta) | Gamma distribution with shape alpha and scale beta. |
gauss(mu=0.0, sigma=1.0) | Gaussian distribution (faster but less thread-safe). |
lognormvariate(mu, sigma) | Log-normal distribution. |
normalvariate(mu=0.0, sigma=1.0) | Normal (Gaussian) distribution. |
vonmisesvariate(mu, kappa) | Von Mises distribution for angles. |
paretovariate(alpha) | Pareto distribution. |
weibullvariate(alpha, beta) | Weibull distribution. |
| Alternative Generators | |
Random([seed]) | Class implementing the default PRNG; can be subclassed. |
SystemRandom() | Class using os.urandom() for system-based randomness. |
Data structures
| Type | Mutable? | Ordered? | Allows Duplicates? | Description |
|---|---|---|---|---|
list | ✅ | ✅ | ✅ | General‑purpose, ordered collection. For sequences, stacks, queues (with deque for speed). |
tuple | ❌ | ✅ | ✅ | Fixed‑size, ordered grouping. Good for records, dictionary keys, function returns. |
dict | ✅ | ✅ (insertion order preserved) | Keys: ❌ | Key‑value mapping. Fast lookups, flexible keys (immutable types). |
set | ✅ | ❌ | ❌ | Unordered collection of unique elements. For membership tests, set algebra. |
frozenset | ❌ | ❌ | ❌ | Immutable set, usable as a dictionary key or set element. |
str | ❌ | ✅ | ✅ | Text sequences. Technically a sequence of Unicode code points. |
range | ❌ | ✅ | ✅ | Memory‑efficient integer sequence, often for looping. |
bytes / bytearray | bytes: ❌bytearray: ✅ | ✅ | ✅ | Sequences of raw bytes for binary data, file I/O, networking. |
Patterns and Methods
| Pattern | Use | Python Tools |
|---|---|---|
| Recursion | Natural for divide‑and‑conquer problems. | Define function that calls itself; manage base cases carefully. |
| List comprehensions | Concise, often faster than loops. | [f(x) for x in items if cond(x)] |
| Generator functions | Lazily produce items; save memory. | yield keyword; pair with itertools. |
| Set operations | Fast membership & deduplication. | .union(), .intersection(), .difference(). |
| String methods | Essential for parsing/text processing. | .split(), .join(), .strip(). |
When to choose what
| Need | Best Choice |
|---|---|
| Fast random access + frequent mutation | list |
| Fixed, unchanging grouping | tuple |
| Key–value lookups | dict |
| Unique elements only | set / frozenset |
| FIFO or LIFO with speed | collections.deque |
| Count/frequency of elements | collections.Counter |
| Maintain sorted order efficiently | sorted() for snapshots1, bisect for incremental inserts2 |
| Work with binary data | bytes / bytearray / array.array |
| Immutable set‑like behavior | frozenset |
| Map missing keys to default values | collections.defaultdict |
| Preserve insertion order (pre‑3.7 guarantee) | collections.OrderedDict |
| Combine multiple mappings into one view | collections.ChainMap |
| Thread‑safe FIFO queue | queue.Queue |
| Thread‑safe stack | queue.LifoQueue |
| Thread‑safe priority queue | queue.PriorityQueue |
| Priority queue (non‑thread‑safe, lightweight) | heapq (list‑based) |
Questions to ask yourself
- What exactly is the problem statement? Can I restate it in my own words?
- What are the inputs? Type, format, constraints, example values.
- What should the output be? Format, type, exact requirements.
- What are the constraints? Time limits, memory limits, input sizes, special cases.
- Do I fully understand all terms and edge conditions? If not, what needs clarification?
- What data structures could model the problem best? List, dict, set, heap, deque, tree, graph, custom class.
- What category does this problem fall into? Sorting, searching, graph traversal, Dynamic Programming, greedy, simulation, math, string processing
- What algorithmic strategies might fit? Brute force, divide‑and‑conquer, memoization, Breadth First Search, Depth First Serach, binary search, sliding window, two‑pointers.
- How will I handle edge cases? Empty input, max/min values, duplicate data, invalid data.
- Will it scale? Estimate complexity (Big O).
Then:
- How would I solve this with pseudo-code? Map logic without syntax distractions.
- Write solution. In any suitable language.
- Test solution. Including edge cases.
Conclusion
This concludes the many lists of Python functions and tools to aid in designing algorithms. A list of good books about algorithms can be found here.
