Popular recipes tagged "common"

Shortest Common Supersequence algorithms (Python)

2013-10-02T12:52:23-07:00

Python recipe 578678 by Rutger Saalmink (approximation, bound, breadth_first_search, common, depth_first_search, sequence, shortest, super).

The Shortest Common Supersequence (SCS) problem is an NP-hard problem (https://en.wikipedia.org/wiki/Shortest_common_supersequence), which occurs in problems originating from various domains, e.g. Bio Genetics. Given a set of strings, the common supersequence of minimal length is sought after. Below a set of algorithms is given, which I used in approximating and/or backtracking the optimal solution(s).

Extended Euclidean Algorithm (Python)

2016-03-03T07:12:28-08:00

Python recipe 578631 by Samuel James Erickson (algorithm, common, discrete, divisor, euclid, extended, gcd, greatest, logarithm). Revision 2.

given input of integers a and b, this program returns GCD(a,b) along with integers x and y such that ax+by=GCD(a,b).

GCD of an arbitrary list (Python)

2010-12-22T00:05:45-08:00

Python recipe 577512 by Jason Schorn (arbitrary, common, divisor, gcd, greatest, list, schorn).

Given an arbitrary list (of length >= 1) of positive integers, return the greatest common divisor (gcd) of the list.

Finding the GCD of a list of numbers (a.k.a. Reducing numbers in a list) (Python)

2010-07-06T18:52:55-07:00

Python recipe 577282 by Stephen Akiki (common, denominator, gcd, greatest, lisst, reduce).

http://akiscode.com/articles/gcd_of_a_list.shtml

This python code snippet allows you to find the GCD of a list of numbers, after this it is a simple matter of diving all the numbers in the list by the GCD to reduce it.

Why this works...

The GCD of a list of numbers [a, b, c] is GCD(GCD(a, b), c). The reduce function does exactly this and thus gives you the GCD of all the numbers in the list.