list comprehensions in python and combinatorics

Question

Suppose there are n channels, each channel has a single numeric value, say i-th channel has value f(i). I am thinking about using python list comprehension to calculate the average of w (1<= w <= n) consecutive and distinct products in these channels.

For example, n = 3,

If w = 1 , return [f(1)+f(2)+f(3)]/3
If w = 2 , return [f(1)f(2)+f(1)f(3)+f(2)f(3)] /3 
If w = 3 , return [f(1)f(2)f(3)]/1

these indexes can be attained by:

[[i,j,k] for i in xrange(2) for j in xrange(2) for k in xrange(2) if i+j+k ==w]

However, these codes cannot be generalized to any n obviously. Thanks in advance for any help !

```itertools``` has combinatoric generators. Put your data in an appropriate container, use those generators to produce the combo's you want then act on them. Is that what you are doing? — wwii, Apr 05 '14 at 03:27

score 1 · Accepted Answer · edited May 23 '17 at 12:32

I'll keep this brief:

Python 2

>>> import itertools
>>> from operator import mul
>>> from __future__ import division
>>> def calc(f, w):
        if w >= 1 and w <= len(f):
            l = [reduce(mul, comb) for comb in itertools.combinations(f, w)]
            return round(sum(l)/len(l), 3)

>>> calc([1,2,3], 2)
3.667
>>> calc([2,2,2,1], 2)
3.0

Python 3

>>> import itertools
>>> from operator import mul
>>> from functools import reduce
>>> def calc(f, w):
        if w >= 1 and w <= len(f):
            l = [reduce(mul, comb) for comb in itertools.combinations(f, w)]
            return round(sum(l)/len(l), 3)

>>> calc([1,2,3], 2)
3.667
>>> calc([2,2,2,1], 2)
3.0

see What's the Python function like sum() but for multiplication? product()? for the multiplication part explanation.

dr jimbob · Answer 2 · 2014-04-05T03:48:57.870

This is a bad example for list comprehensions when N is really large, as you'll need N variables with for i in xrange(2) when each is either on or off, but its rather straightforward to do with itertools.combination

For example to clone your N=3 example:

results = []
for w in range(1,4):
    results += [[i,j,k] for i in xrange(2) for j in xrange(2) for k in xrange(2) if i+j+k ==w]

where you get results as: [[0, 0, 1], [0, 1, 0], [1, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Now the following using itertools.combination is trivial to scalably extend to larger N.

import itertools
results = []
N=3
for w in range(1,N+1):
    results += list(itertools.combinations(range(N),w))

where you get results as [(0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)], that is return the indices of the variables that are non-zero.

This can be trivially turned into the other form, e.g.:

for index_tuple in results:
    new = [0]*N
    for i in index_tuple:
        new[i] = 1
    new_results.append(new)

where new_results has the same form [[1, 0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 0], [1, 0, 1], [0, 1, 1], [1, 1, 1]] and can be trivially extended to larger N. (Granted it's probably better to keep it in the first form, or use something like numpy for efficient use of masking arrays).

list comprehensions in python and combinatorics

2 Answers2