Python itertools module has built-in functions for permutations, combinations, cycles and products.
So the Python programmers can focus on building the next killer-apps :) which will dominate the whole world, instead
of reading obtuse treatises, papers, and other publications on algorithms for generating combinatorial objects.
Here we list the combinatorial capabilities of Python (versions 2.6+) in the itertools module.
Permutations
itertools.permutation create a permutation object from an iterable input or string. You can list
the successive permutations by using object.next() or by creating a list (a bad idea if the size of the object is large!)
list(object). Here is an example:
x = itertools.permutation(range(7))
try:
while True:
print x.next()
except:
pass
You can also do:
x = itertools.permutation(range(7))
for i, e in enumerate(list(x)):
print i+1, e
Converting to a list give rise to a dangerous situation where you can run out of memory!. but if you know that it can be safely stored,
by all means use a list conversion.
Permutations can also accept an extra parameter r so you can generate all permutations of size n of the object taken r at a time.
The number of elements in such permutations is given by n!/(n-r)!. If r is not specified, then the number of permutations is n!
which look innocous.(50! is nothing to sneeze at).
combinations
import itertools
seq = range(6)
x = itertools.combinations(seq, 3)
try:
for i, e in list(enumerate(x)):
f = [y for y in seq if y not in e]
print i+1, list(e), f
except:
pass
The output of permutations and combinations are tuples for fast execution of the functions, and have to be typecast to a list. Itertools also provide combinations with replacement. The best way to see the difference with the standard combinations is to see them in action from the command line:
x = combinations_with_replacement([1,2,3,4], 2)
y = combinations([1,2,3,4], 2)
list(x)
[(1, 1),
(1, 2),
(1, 3),
(1, 4),
(2, 2),
(2, 3),
(2, 4),
(3, 3),
(3, 4),
(4, 4)]
list(y)
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
Cartesion products
Itertools has cartesian products! So instead of writing (this from the documentation)
((x,y) for x in A for y in B)
we simply write product(A,B)
Wait, how about the cartesian product of A with itself?
you can write product(A,A) or if you want more, product(A,A,A,A). The latter can be written as
product(A, repeat=4). Python programmers can be lazy as Perl programmers!
cycle
Not strictly referrring to a mathematical object. Rather it refers to the way an element in an
iterable is accessed. Instead of stopping at the last element, the access is cycled back to the first element.
Try this on the command line (not running in a script file)
x = cycle((1,2,3,4))
while True:
print x.next()
You will notice that this loop never terminates, and after the 4 is printed, the next element to be printed is the first element.
Type Ctrl-C to abort the printing.
Aside from these basic combinatorial objects, Itertools provide now a
repeat function! For example, a list of 100
elements with all values equal to 5: [5] * 100 can now be written as itertools.repeat(5, 100). Easier to understand for beginners.
Dont you just love Python?
Hopefully, Python will offer genuine cycle objects (where you can multiply two cycles) and derangements with basic functions such as nPr and nCr. These combinatorial features are solutions waiting for problems and applications!
TO BE CONTINUED.
