CODEWITHSUNDEEP
pythonpython-2.7tuplescounterlist-comprehension
ACVentures
ACVentures

Reputation: 81

All possible combinations of value-pairs (2-item tuples) in a sequence - PYTHON 2.7

I'm having a math brain fart moment, and google has failed to answer my quandary.

Given a sequence or list of 2 item tuples (from a Counter object), how do I quickly and elegantly get python to spit out a linear sequence or array of all the possible combinations of those tuples? My goal is trying to find the combinations of results from a Counter object.....

For example clarity, if I have this sequence: 

[(500, 2), (250, 1)]

Doing this example out manually by hand, it should yield these results:

250, 500, 750, 1000, 1250.

Basically, I THINK it's a*b for the range of b and then add the resulting lists together... I've tried this (where c=Counter object):

res = [[k*(j+1) for j in range(c[k])] for k in c]

And it will give me back:

res = [[250], [500, 1000]]

So far so good, it's going through each tuple and multiplying x * y for each y... But the resulting list isn't full of all the combinations yet, the first list [250] needs to be added to each element of the second list. This would be the case for any number of results I believe.

Now I think I need to take each list in this result list and add it to the other elements in the other lists in turn. Am I going about this wrong? I swear there should be a simpler way. I feel there should be a way to do this in a one line list comp.

Is the solution recursive? Is there a magic import or builtin method I don't know about? My head hurts......

Upvotes: 1

Views: 601

Answers (2)

jfs
jfs

Reputation: 414265

v*f multiplication from @DSM's answer could be avoided:

>>> from itertools import product
>>> terms = [(500, 2), (250, 1)]
>>> map(sum, product(*[xrange(0, v*a+1, v) for v, a in terms]))
[0, 250, 500, 750, 1000, 1250]

To get a sorted output without duplicates:

from itertools import groupby, imap
from operator import itemgetter

it = imap(itemgetter(0), groupby(sorted(it)))

though sorted(set(it)) that you use is ok in this case.

Upvotes: 0

DSM
DSM

Reputation: 353099

I'm not entirely sure I follow you, but maybe you're looking for something like

from itertools import product

def lincombs(s):
    terms, ffs = zip(*s)
    factors = product(*(range(f+1) for f in ffs))
    outs = (sum(v*f for v,f in zip(terms, ff)) for ff in factors if any(ff))
    return outs

which gives

>>> list(lincombs([(500, 2), (250, 1)]))
[250, 500, 750, 1000, 1250]
>>> list(lincombs([(100, 3), (10, 3)]))
[10, 20, 30, 100, 110, 120, 130, 200, 210, 220, 230, 300, 310, 320, 330]

Upvotes: 2

Related Questions